161. One Edit Distance — разбор задачи

1. Условие задачи

Дано: две строки s и t. Они могут состоять из строчных и заглавных английских букв и цифр. Пустые строки тоже разрешены.

Разрешено: выполнить над строкой s одну из трёх операций:

вставить один символ;
удалить один символ;
заменить один символ на другой.

Нужно: вернуть True, если строку s можно превратить в t ровно за одну операцию. Если потребуется ноль операций или больше одной, возвращаем False.

Последнее слово здесь самое важное: ровно одна операция. Поэтому одинаковые строки не подходят.

s = "ab", t = "acb"  → True

Между a и b можно вставить c.

s = "", t = ""  → False

Строки уже равны, то есть нужно ноль операций, а не одна.

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

0 <= len(s), len(t) <= 10^4;
строки содержат английские буквы и цифры;
вставка, удаление или замена считаются одной операцией.

2. Решение

Ключевое наблюдение

Сначала посмотрим только на длины строк.

Если длины отличаются больше чем на 1, одной вставкой или удалением это не исправить. Ответ сразу False.
Если длины равны, единственная возможная операция - замена.
Если длины отличаются на 1, возможна только вставка в короткую строку или, что то же самое, удаление из длинной.

Теперь идём слева направо до первого несовпадения. Всё до него уже одинаково и редактировать там ничего не нужно. В точке несовпадения мы мысленно тратим нашу единственную операцию, после чего оставшиеся части строк обязаны полностью совпасть.

Именно такой однопроходный подход приводит официальный editorial LeetCode.

Первое решение: со слайсами

Для начала сделаем s более короткой строкой. Если строки разной длины, нам тогда останется рассматривать только вставку символа в s. Это избавляет код от зеркального случая с удалением.

Дальше ищем первое несовпадение s[i] != t[i]:

при равных длинах мысленно заменяем s[i] на t[i] и сравниваем хвосты после этих символов: s[i + 1:] == t[i + 1:];
если t длиннее на один символ, мысленно вставляем t[i] в строку s и сравниваем s[i:] == t[i + 1:].

Если несовпадения вообще не нашлось, короткая строка целиком совпадает с началом длинной. Тогда ответ True только в одном случае: в t остался ровно один лишний символ в конце.

Алгоритм со слайсами

Если s длиннее t, меняем строки местами.
Если t длиннее s больше чем на один символ, возвращаем False.
Идём по индексам короткой строки до первого несовпадения.
При равных длинах пропускаем по одному символу в обеих строках и сравниваем оставшиеся хвосты.
При разных длинах пропускаем один символ только в длинной строке и сравниваем хвосты.
Если несовпадений не было, проверяем, что длинная строка содержит ровно один дополнительный символ.

Код на Python: решение со слайсами

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        # 1. Пусть s будет не длиннее t
        if len(s) > len(t):
            return self.isOneEditDistance(t, s)

        # 2. Разницу больше единицы одной операцией не исправить
        if len(t) - len(s) > 1:
            return False

        # 3. Ищем первое несовпадение
        for i in range(len(s)):
            if s[i] != t[i]:
                if len(s) == len(t):
                    # Замена: пропускаем несовпавший символ в обеих строках
                    return s[i + 1:] == t[i + 1:]

                # Вставка в s: пропускаем символ только в длинной t
                return s[i:] == t[i + 1:]

        # 4. Общий префикс совпал:
        # одна операция нужна только при одном лишнем символе в t
        return len(t) == len(s) + 1

Визуализация решения со слайсами

Возьмём:

s = "ab"
t = "acb"

Шаг	`i`	`s[i]`	`t[i]`	Что делаем
1	`0`	`a`	`a`	Символы равны, идём дальше
2	`1`	`b`	`c`	Первое несовпадение
3	`1`	-	-	`t` длиннее, пропускаем `t[1]`
4	-	-	-	Сравниваем `s[1:] == t[2:]`, то есть `"b" == "b"`

Хвосты совпали, значит, достаточно вставить c в строку s. Ответ True.

Почему решение со слайсами работает

До первого несовпадения строки одинаковы, поэтому тратить операцию в общем префиксе бессмысленно.

В первом несовпадении тип допустимой операции однозначно определяется длинами. При равных длинах мы обязаны заменить символ и после этого сравнивать позиции со сдвигом 0. При разнице длин 1 мы обязаны пропустить символ длинной строки и после этого сравнивать позиции со сдвигом 1.

Если оставшиеся хвосты равны, найденной операции достаточно. Если в хвостах есть ещё одно несовпадение, потребовалась бы вторая операция, поэтому ответ False.

Второе решение: без слайсов и без дополнительной памяти

Слайсы делают первое решение коротким, но в Python выражение вроде s[i:] создаёт новую строку. Поэтому в худшем случае на копирование хвостов требуется O(N) дополнительной памяти. Это отдельно отмечено в официальном editorial и часто обсуждается в комментариях к нему.

Чтобы получить честные O(1) по памяти, не будем создавать хвосты. Сравним их на месте с помощью двух указателей:

i смотрит на текущий символ короткой строки s;
j смотрит на текущий символ длинной строки t;
edits хранит количество уже использованных операций.

Если символы равны, двигаем оба указателя. При первом несовпадении увеличиваем edits:

при равных длинах это замена, поэтому двигаем оба указателя;
если t длиннее, это вставка в s, поэтому двигаем только j.

При втором несовпадении сразу возвращаем False. Такой подход лежит в основе популярных пользовательских решений без слайсов, например [Python3] Pointer One Pass Solution и [Python3] O(1) space solution.

Алгоритм без слайсов

Если s длиннее t, меняем строки местами.
Если разница длин больше 1, возвращаем False.
Ставим указатели i = 0, j = 0 и счётчик edits = 0.
Пока оба указателя внутри строк, сравниваем s[i] и t[j].
Если символы равны, двигаем оба указателя.
Если символы различаются, учитываем одну операцию. При второй операции возвращаем False.
При равных длинах после несовпадения двигаем оба указателя, при разных - только указатель длинной строки.
Если после цикла в длинной строке остался символ, учитываем ещё одну вставку.
Возвращаем True, только если набралась ровно одна операция.

Код на Python: решение без слайсов

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        # 1. Пусть s будет не длиннее t
        if len(s) > len(t):
            s, t = t, s

        # 2. Одной операцией такую разницу не исправить
        if len(t) - len(s) > 1:
            return False

        i = 0
        j = 0
        edits = 0

        # 3. Сравниваем символы на месте, не создавая подстрок
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
                j += 1
                continue

            # Нашли очередное несовпадение
            edits += 1
            if edits > 1:
                return False

            if len(s) == len(t):
                # Замена: пропускаем символ в обеих строках
                i += 1
                j += 1
            else:
                # Вставка в s: пропускаем символ только в длинной t
                j += 1

        # 4. В t мог остаться один символ в самом конце
        if j < len(t):
            edits += 1

        return edits == 1

Визуализация решения без слайсов

Снова возьмём s = "ab" и t = "acb".

Шаг	`i`	`j`	Сравнение	`edits`	Действие
1	`0`	`0`	`a == a`	`0`	Двигаем `i` и `j`
2	`1`	`1`	`b != c`	`1`	`t` длиннее, двигаем только `j`
3	`1`	`2`	`b == b`	`1`	Двигаем `i` и `j`
4	`2`	`3`	обе строки закончились	`1`	Возвращаем `True`

Мы не создавали строки "b" и "b", а сравнили те же символы по индексам.

Почему указатели не пропускают ответ

После нормализации s не длиннее t, поэтому возможны только два случая.

Длины равны. Единственная допустимая операция - замена. После несовпадения нужно сдвинуть оба указателя, и все следующие символы должны совпасть.
t длиннее на один символ. Единственная допустимая операция - вставка в s. На несовпадении нужно пропустить только символ t[j], после чего строки снова должны синхронизироваться.

Если короткая строка закончилась раньше, а в t остался последний символ, это тоже одно редактирование: вставка в конец. Счётчик edits гарантирует, что мы принимаем только строки с ровно одной, а не с нулём или двумя операциями.

Краевые случаи

Одинаковые строки: s = "abc", t = "abc" → False. Несовпадений нет, edits == 0.
Обе строки пустые: s = "", t = "" → False. Для превращения не нужна ни одна операция.
Одна строка пустая, в другой один символ: s = "", t = "a" → True. Достаточно одной вставки.
Разница длин больше единицы: s = "a", t = "abc" → False. Нужны как минимум две вставки.
Замена в начале: s = "abc", t = "xbc" → True.
Замена в конце: s = "abc", t = "abd" → True.
Вставка в середине: s = "ab", t = "acb" → True.
Вставка в конце: s = "ab", t = "abc" → True. Основной цикл закончится, а оставшийся символ учтётся после него.
Два несовпадения: s = "abc", t = "axd" → False. На втором несовпадении сразу выходим.
Удаление из исходной s: s = "acb", t = "ab" → True. В начале мы поменяем строки местами и сведём удаление к симметричной вставке в короткую строку.

3. Сложность алгоритма

Обозначим через N длину более длинной строки.

Решение со слайсами

Поиск первого несовпадения занимает до O(N).
Создание слайсов копирует оставшиеся символы и занимает до O(N) времени.
Сравнение двух полученных хвостов также занимает до O(N).
Одновременно создаются подстроки суммарной длины до O(N).

Итог по времени: O(N).

Итог по памяти: O(N) из-за слайсов.

Решение без слайсов

Каждый указатель движется только вперёд и проходит свою строку не более одного раза.
Каждое сравнение и изменение указателя занимает O(1).
Храним только два указателя и счётчик операций.

Итог по времени: O(N).

Итог по памяти: O(1).

Вывод

Главный паттерн задачи: на первом несовпадении длины строк подсказывают, какую операцию нужно выполнить. Равные длины означают замену и сдвиг двух указателей, разница в один символ означает вставку или удаление и сдвиг только по длинной строке.

Слайсы дают очень короткое и наглядное решение, близкое к официальному editorial. Но если на собеседовании требуют O(1) дополнительной памяти, те же хвосты нужно сравнивать на месте двумя указателями.

Официальный разбор: leetcode.com/problems/one-edit-distance/editorial
Решения пользователей: leetcode.com/problems/one-edit-distance/solutions

🐆