Что такое расстояние Левенштейна и как его вычислить?

Расстояние Левенштейна — это минимальное количество элементарных операций, которыми одну строку можно превратить в другую. Допускаются три операции, каждая «стоит» единицу:

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

Например, расстояние между kitten и sitting равно 3:

1. kitten → sitten (замена k → s)
2. sitten → sittin (замена e → i)
3. sittin → sitting (вставка g)

Где применяется: проверка орфографии, автодополнение, нечёткий поиск, биоинформатика (сравнение ДНК), сравнение версий.

Алгоритм — классическое динамическое программирование. Строим таблицу dp, где dp[i][j] — расстояние между первыми i символами строки a и первыми j символами строки b.

def levenshtein(a: str, b: str) -> int:
    n, m = len(a), len(b)
    # dp[i][j] — расстояние между a[:i] и b[:j]
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # базовые случаи: превратить строку в пустую = удалить все символы
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,        # удаление
                dp[i][j - 1] + 1,        # вставка
                dp[i - 1][j - 1] + cost  # замена (или совпадение)
            )
    return dp[n][m]


print(levenshtein("kitten", "sitting"))  # 3
print(levenshtein("flaw", "lawn"))        # 2

Сложность: время O(n*m), память O(n*m). Память легко оптимизируется до O(min(n, m)), потому что для вычисления текущей строки таблицы нужна только предыдущая:

def levenshtein_optimized(a: str, b: str) -> int:
    if len(a) < len(b):
        a, b = b, a
    previous = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        current = [i]
        for j, cb in enumerate(b, 1):
            cost = 0 if ca == cb else 1
            current.append(min(previous[j] + 1, current[j - 1] + 1, previous[j - 1] + cost))
        previous = current
    return previous[-1]