Сложность: medium
Даны две строки s и t. Верните true, если они отличаются ровно на одну операцию редактирования, иначе верните false.
Строка s считается отличающейся на одну операцию редактирования от строки t, если можно:
- Вставить ровно один символ в строку s, чтобы получить t.
- Удалить ровно один символ из строки s, чтобы получить t.
- Заменить ровно один символ в строке s на другой символ, чтобы получить t.
Пример:
Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.
👨💻 Алгоритм:
1⃣Проверка длины строк:
Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку.
Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false.
2⃣Сравнение строк посимвольно:
Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t.
Если находите различающийся символ:
Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false.
Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false
3⃣Проверка на возможное добавление символа в конец s:
Если после посимвольного сравнения не было найдено различий на всей длине s и t длиннее s на один символ, это означает, что t можно получить добавлением одного символа в конец s. В этом случае верните true.
В противном случае верните false, так как это означает, что t либо имеет больше отличий, либо такой же размер как s без возможности привести их к равенству одной операцией редактирования.
😎 Решение:
class Solution {
public boolean isOneEditDistance(String s, String t) {
int ns = s.length();
int nt = t.length();
if (ns > nt) return isOneEditDistance(t, s);
if (nt - ns > 1) return false;
for (int i = 0; i < ns; i++) {
if (s.charAt(i) != t.charAt(i)) {
if (ns == nt) {
return s.substring(i + 1).equals(t.substring(i + 1));
} else {
return s.substring(i).equals(t.substring(i + 1));
}
}
}
return (ns + 1 == nt);
}
}Ставь 👍 и забирай 📚 Базу знаний