3 варианта решения популярной задачи

Постановка задачи

Написать функцию, которая вернет true, если из строки s можно получить строку t, совершив не более, чем одно из 3х изменений: удаление одного символа из s, добавление одного символа в s, замена одного символа в s.

  class Solution {     /*     Вернуть true, если из строки s можно получить строку t,     совершив не более, чем одно из 3х изменений]:     - удалить из s один символ     - добавить в s один символ     - заменить в s один символ     s = aaa t = aaa -> true     s = baaa t = aaa -> true     s = aaa t = aaab -> true     s = aba t = aca -> true     s = badca t = babba -> false     s = badca t = badcaaa -> false     */     boolean check(String s, String t) {     }   }

Общие упрощения

Удаление символа из строки s эквивалентно добавлению символа в строку t. Перейдем от 3 возможных изменений к 2 возможным, если будем менять местами s и t, чтобы s всегда была не короче t:

boolean check(String s, String t) {   if(s.equals(t)) return true;   if(s.length() < t.length()) {     String q = s;      s = t;      t = q;   }   if(s.length() - t.length() > 1) return false; }

1 вариант решения

Решим более простую задачу. Предположим, что изменение всегда проводится с начальными символами строк. Напишем вспомогательную функцию:

boolean checkHelper(String s, String t) {   return s.substring(1).equals(t) || s.substring(1).equals(t.substring(1)); }

Посчитаем, сколько символов в головах строк совпадают. И применим вспомогательную функцию к хвостам строк:

boolean check(String s, String t) {   if(s.equals(t)) return true;   if(s.length() < t.length()) {     String q = s;      s = t;      t = q;   }   if(s.length() - t.length() > 1) return false;   int i = 0;   for(; i < t.length(); i++) {     if(s.charAt(i) != t.charAt(i)) break;   }   return checkHelper(s.substring(i), t.substring(i)); }

Проверим решение:

  public static void main(String[] args) {     Solution s = new Solution();     System.out.println("check true");     System.out.println(s.check("aaa", "aaa"));     System.out.println(s.check("baaa", "aaa"));     System.out.println(s.check("aaa", "baaa"));     System.out.println(s.check("caaa", "baaa"));     System.out.println(s.check("aaa", "aaab"));     System.out.println(s.check("aaab", "aaa"));     System.out.println(s.check("aaab", "aaac"));     System.out.println(s.check("aaba", "aaa"));     System.out.println(s.check("aaa", "aaba"));     System.out.println(s.check("aaba", "aaca"));     System.out.println("check false");     System.out.println(s.check("bcaaa", "aaa"));     System.out.println(s.check("aaa", "bcaaa"));     System.out.println(s.check("efaaa", "ghaaa"));     System.out.println(s.check("aaa", "aaabc"));     System.out.println(s.check("aaabc", "aaa"));     System.out.println(s.check("aaaef", "aaagh"));     System.out.println(s.check("aabca", "aaa"));     System.out.println(s.check("aaa", "aabca"));     System.out.println(s.check("aaefa", "aagha"));   }

check true true true true true true true true true true true check false false false false false false false false false false

2 вариант решения

Можно обойтись без substring. Но код будет более громоздким:

boolean check(String s, String t) {   if(s.equals(t)) return true;   if(s.length() < t.length()) {     String q = s;      s = t;      t = q;   }   if(s.length() - t.length() > 1) return false;   int i = 0;   for(; i < t.length(); i++) {     if(s.charAt(i) != t.charAt(i)) break;   }   return checkHelper(s, t, i); }  boolean checkHelper(String s, String t, int i) {   int si = i + 1;   int ti = (s.length() == t.length()) ? (i + 1) : i;   for(; ti < t.length(); si++, ti++) {     if(s.charAt(si) != t.charAt(ti))        return false;   }   return true; }

3 вариант решения

Вынесем во вспомогательную функцию код подсчета совпадающих символов в головах строк:

int checkHelper(String s, String t) {   int i = 0;   for(; i < t.length(); i++) {     if(s.charAt(i) != t.charAt(i)) break;   }   return i; }

Решим задачу через подсчет длин общих подпоследовательностей в головах строк и в хвостах.

String reverse(String s) {   return new StringBuilder(s).reverse().toString(); }  boolean check(String s, String t) {   if(s.equals(t)) return true;   if(s.length() < t.length()) {     String q = s;      s = t;      t = q;   }   if(s.length() - t.length() > 1) return false;   int i = checkHelper(s, t);   int j = checkHelper(reverse(s), reverse(t));   return i + j >= t.length() - 1; }

Итог

Все решения работают за линейное время. Первое решение лично мне видится более читаемым. Но в нем легко сделать ошибку во вспомогательной функции с substring — при неправильном порядке условий в логическом ИЛИ будет ошибка выхода за границы массива.

Спасибо, что прочитали мою статью. Подписывайтесь на мой канал: