Расстояние редактирования (расстояние Левенштейна) — минимальное число вставок, удалений и замен, превращающих одну строку в другую. Оно лежит в основе исправления опечаток и нечёткого поиска.

Три операции

  • вставка буквы;
  • удаление буквы;
  • замена буквы другой.

Каждая стоит 1. Для kitten и sitting ответ 3: заменить k на s, заменить e на i, вставить g.

Состояние и переход

  • Состояние: dp[i][j] — минимальное число операций, превращающих первые i букв a в первые j букв b.
  • База: dp[i][0] = i (удалить всё), dp[0][j] = j (вставить всё).
  • Та же буква (a[i-1] == b[j-1]): dp[i][j] = dp[i-1][j-1].
  • Иначе: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), то есть удаление, вставка или замена.
  • Ответ: dp[n][m].
Таблица расстояния редактирования для "kitten" и "sitting" и оптимальный путь
Таблица расстояния редактирования для "kitten" и "sitting" и оптимальный путь
python
def edit_table(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i                       # delete i letters
    for j in range(m + 1):
        dp[0][j] = j                       # insert j letters
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]            # same letter: free
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],       # delete a[i-1]
                                   dp[i][j - 1],       # insert b[j-1]
                                   dp[i - 1][j - 1])   # replace
    return dp

dp = edit_table("kitten", "sitting")
for row in dp:
    print(*row)
print("distance:", dp[-1][-1])

Восстановление операций