Задача с собеседования в Zoho

Даны две строки: word1 и word2. Верните минимальное количество операций, требуемых для преобразования строки word1 в строку word2.
Вы можете выполнять следующие три операции над словом:
- вставить символ
- удалить символ
- заменить символ

Пример 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (заменить 'h' на 'r')
rorse -> rose (удалить 'r')
rose -> ros (удалить 'e')

Пример 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (удалить 't')
inention -> enention (заменить 'i' на 'e')
enention -> exention (заменить 'n' на 'x')
exention -> exection (заменить 'n' на 'c')
exection -> execution (вставить 'u')

Ограничения:
0 <= word1.length, word2.length <= 500
word1 и word2 состоят из строчных английских букв

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задача помечена тегом "Dynamic Programming" и является классическим примером задачи на вычисление "расстояния Левенштейна". Используем восходящее dp с табуляцией.

Сначала разберём базовое решение, а потом оптимизируем:
Заполняем таблицу размером (len(word1) + 1) × (len(word2) + 1), где dp[i][j] - минимальное кол-во операций, необходимое для превращения первых i символов word1 в первые j символов word2.

i и j - это кол-во символов, поэтому dp[0][j] соответствует пустой word1, dp[i][0] - пустой word2.
Базовый случай, когда одна из строк пустая:
word1 пустая: нужно вставить все символы word2 (j вставок);
word2 пустая: нужно удалить все символы word1 (i удалений).

Остальные ячейки заполняем, смотря на последние символы текущих префиксов (word1[i-1] и word2[j-1]):
Если символы совпадают, нам не нужно ничего с ними делать, копируем значение из левой верхней ячейки;
Если символы не совпадают, есть три варианта действий, выбираем минимальный по кол-ву операций:
1. Замена: dp[i-1][j-1] + 1 - заменяем последний символ word1 на последний символ word2;
2. Удаление: dp[i-1][j] + 1 - удаляем последний символ из word1;
3. Вставка: dp[i][j-1] + 1 - вставляем последний символ word2 в word1.

Оптимизируем:
Храним не всю таблицу, а две переменные: prev (предыдущая строка, на первом шаге - первая строка таблицы) и cur (текущая строка, вначале заполнена нулями).
Если длина word1 меньше длины word2, меняем строки местами: более короткая строка становится word2, внутренний цикл идёт по ней, оптимизируя память до O(min(m, n)).

Во внешнем цикле: проходим по всем символам word1:
- в начале каждой итерации устанавливаем первый эл-т текущей строки: cur[0] = i. Это соответствует случаю, когда word2 пустая, поэтому нужно удалить все i символов из word1.
Во внутреннем: проходим по word2:
- символы совпадают: копируем значение из левой верхней ячейки (prev[j-1]);
- не совпадают: берём минимум из трёх значений:
prev[j-1] - замена символа word1[i-1] на word2[j-1]; обе строки становятся короче на 1, в таблице dp это диагональ.
prev[j] - удаление символа word1[i-1]; word1 становится короче, word2 - той же длины, в таблице это верх.
cur[j-1] - вставка символа word2[j-1] в word1; word2 - короче, word1 - той же длины, в таблице это значение слева.
+ 1, так как любая операция требует одного действия.

После заполнения строки меняем местами prev и cur, текущая строка становится предыдущей для следующей итерации.
После завершения циклов prev содержит последнюю заполненную строку, а её последний эл-т является ответом.

Сложность
O(mn) - по времени (проходим по всем парам символов)
O(min(m, n)) - по памяти

Код
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
if len(word1) < len(word2):
word1, word2 = word2, word1

prev = list(range(len(word2) + 1))
cur = [0] * (len(word2) + 1)

for i in range(1, len(word1) + 1):
cur[0] = i
for j in range(1, len(word2) + 1):
if word1[i-1] == word2[j-1]:
cur[j] = prev[j-1]
else:
cur[j] = min(prev[j-1], prev[j], cur[j-1]) + 1

prev, cur = cur, prev

return prev[-1]

@algoses