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));
}Проверим решение:
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
false2 вариант решения
Можно обойтись без 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 — при неправильном порядке условий в логическом ИЛИ будет ошибка выхода за границы массива.
Спасибо, что прочитали мою статью. Подписывайтесь на мой канал:
