Edit Distance

Пусть edits(i, j) — минимальное число изменений, необходимых, чтобы превратить суффикс word1[i:] в word2[j:]. Посмотрим на первые буквы двух суффиксов. Если они совпадают, оставим их и передвинем оба индекса: совпадающую букву никогда не нужно изменять, а любой план, в котором на неё тратится изменение, можно заменить планом, который её сохраняет, не увеличивая длину.

Если буквы различаются, какое-то изменение должно затронуть word1[i] или добавить word2[j], и есть ровно три способа. Заменить word1[i] на word2[j] и передвинуть оба индекса: edits(i+1, j+1). Удалить word1[i] и передвинуть только i: edits(i+1, j). Вставить word2[j] перед ней и передвинуть только j: edits(i, j+1). Ответ равен 1 плюс минимум из трёх вариантов. Когда в word1 заканчиваются буквы, вставляем оставшуюся часть word2, что стоит m - j; когда в word2 заканчиваются буквы, удаляем оставшуюся часть word1, что стоит n - i.

Алгоритм работает медленно, потому что при каждом несовпадении запускаются три вызова. Для двух слов из 15 букв, в которых нет общих букв, это около 6.7 × 10^10 вызовов, а в больших тестах по 500 букв в каждом слове. Однако существует всего (n+1) × (m+1) различных пар (i, j), поэтому почти каждый вызов повторяет уже сделанный ранее.

Состояние. Пусть dp[i][j] — минимальное количество правок, необходимых, чтобы превратить первые i букв word1 в первые j букв word2. Индекс 0 обозначает пустой префикс.

Переходы. Сравните последние буквы двух префиксов: word1[i-1] и word2[j-1]. Если они равны, оставьте их: dp[i][j] = dp[i-1][j-1] — ячейка по диагонали сверху слева. Если нет, выполните одну правку и выберите минимум из трёх соседних ячеек. Диагональная ячейка dp[i-1][j-1] означает замену word1[i-1] на word2[j-1]. Ячейка сверху, dp[i-1][j], означает удаление word1[i-1]. Ячейка слева, dp[i][j-1], означает вставку word2[j-1] в конец.

Базовая строка и столбец. В отличие от многих задач с таблицами, здесь они не заполнены нулями. Чтобы превратить i букв в пустой префикс, нужно выполнить i удалений, поэтому dp[i][0] = i. Чтобы получить j букв из ничего, нужно выполнить j вставок, поэтому dp[0][j] = j. Каждая ячейка использует ячейку сверху, слева и по диагонали, поэтому при заполнении строка за строкой, слева направо, все нужные значения уже будут вычислены. Ответ — dp[n][m].

Вот таблица для преобразования spot в stop; столбцы соответствуют префиксам "", s, st, sto, stop. Строка "" — это [0, 1, 2, 3, 4], строка s — [1, 0, 1, 2, 3], строка sp — [2, 1, 1, 2, 2], строка spo — [3, 2, 2, 1, 2], а строка spot — [4, 3, 2, 2, 2]. Рассмотрим несколько ячеек. s и s совпадают, поэтому значение копируется из диагональной ячейки — 0. sp и st не совпадают: значения в соседних ячейках — 0 по диагонали, 1 сверху и 1 слева, поэтому значение равно 1 + 0 = 1 — одна замена. spo и sto совпадают по букве o, поэтому копируется значение 1. В последней ячейке spot и stop сравниваются буквы t и p: значения в соседних ячейках — 1, 2 и 2, поэтому ответ равен 1 + 1 = 2.

В таблице (n+1) × (m+1) ячеек, на обработку каждой из которых уходит постоянное время; для двух слов длиной 500 букв это около 2.5 × 10^5 шагов. Рекурсия с мемоизацией заполняет те же ячейки, но глубина рекурсии может достигать n + m вызовов, что превышает стандартный лимит Python в 1000.

Строка i считывает только строку i-1 и свои ячейки слева. После завершения строки строки выше больше никогда не считываются. Храни два массива: prev для завершённой строки и cur для строки, которую ты заполняешь, и меняй их местами после каждой строки. Переходы не меняются: диагональ — это prev[j-1], сверху — prev[j], а слева — cur[j-1].

Базовый столбец не исчезает. Теперь он находится в первой ячейке каждой строки, поэтому установи cur[0] = i перед заполнением строки i. Строка 0 начинается с [0, 1, 2, ..., m] — это базовая строка.

Чтобы превратить word2 в word1, требуется столько же правок, потому что каждая вставка становится удалением, а каждое удаление — вставкой. Поэтому можно поменять слова местами и выполнять строки вдоль более короткого слова. Тогда каждая строка будет содержать min(n, m) + 1 чисел вместо таблицы размером до 251,001 ячейки, а объём работы останется O(n × m).