Логотип YeaHub
Войти
Назад

Строки на расстоянии редактирования не более 1 (One Edit Distance)

3

GoJavaJavaScriptPython

Строки

Яндекс

Условие:

Даны две строки s1 и s2, состоящие из строчных латинских букв. Требуется определить, находятся ли они на «расстоянии редактирования» ровно 1 — то есть можно ли превратить одну строку в другую ровно одной из трёх операций:

  • заменить один символ (если строки одинаковой длины);

  • вставить один символ (если вторая строка длиннее первой на 1);

  • удалить один символ (если первая строка длиннее второй на 1).

Если строки идентичны, либо отличаются больше чем на одну операцию, либо разница в длине больше 1 — функция должна вернуть false.

Входные данные:
Две строки s1 и s2.

Выходные данные:
true, если строки отличаются ровно одной операцией редактирования, иначе false.

Ограничения:

  • 0 <= s1.length, s2.length <= 10^4

  • строки состоят только из строчных латинских букв

Примеры:

Вход: s1 = "pale", s2 = "ple"   → Выход: true   (удалён символ "a")
Вход: s1 = "cab",  s2 = "cf"    → Выход: false  (несовпадение более чем в одной позиции при сдвиге)
Вход: s1 = "abc",  s2 = "abc"   → Выход: false  (строки идентичны, ни одной операции не требуется)
Вход: s1 = "abc",  s2 = "abd"   → Выход: true   (заменён один символ)
Loading...