Постановка задачи
Написать функцию, которая вернет 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));
}
Проверим решение:
Hidden text
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 - при неправильном порядке условий в логическом ИЛИ будет ошибка выхода за границы массива.
Спасибо, что прочитали мою статью. Подписывайтесь на мой канал:
wataru
Частая ошибка в таких статьях: вы или сложную интересную задачу берите, или тогда объясняйте ее "для самых маленьких". С нуля, по шагам, чтобы человек не в теме смог понять, как дойти до такого решения.
Потому что читатели, или еще на этапе чтения задачи сразу придумывают решение и им статья не интересна, или не въезжают, а как так получилось вообще, и им эта статья бесполезна.
В данном случае стоит обсудить переборное решение. Потом привести некоторые наблюдения: длины равны - замена, одна длиннее на 1 символ - вставка; При замене префикс и суфиксы должны совпадать. При вставке вот такой префикс и суффиксы совпадают. Показать их на примерах/картинках. Показать на примерах/картинках логику всех проверок. И только потом приводить код. Вы же тут сразу вываливаете три варианта одного и того же по сути решения, акцентируя внимание на каких-то деталях реализации, что, в общем-то, никому не интересно.
apachik
поддерживаю!
и не забыть про доказательство работы за линейное время,
ибо при наличии подобных конструкций, это совсем не очевидно:
>
s.substring(1).equals(t)