← Назад к ДП

Расстояние Левенштейна

Минимальное количество операций для преобразования одной строки в другую

🐍 Python
s1 = input()
s2 = input()
n, m = len(s1), len(s2)

# Оптимизация: делаем s1 короче
if n > m:
    s1, s2 = s2, s1
    n, m = m, n

c = list(range(n + 1))

for i in range(1, m + 1):
    p, c = c, [i] + [0] * n
    for j in range(1, n + 1):
        a = p[j] + 1           # удаление
        d = c[j - 1] + 1       # вставка
        ch = p[j - 1]          # замена
        if s1[j - 1] != s2[i - 1]:
            ch += 1
        c[j] = min(a, d, ch)

print(c[-1])
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    
    int n = s1.length(), m = s2.length();
    
    // Оптимизация: делаем s1 короче
    if (n > m) {
        swap(s1, s2);
        swap(n, m);
    }
    
    vector<int> c(n + 1);
    for (int j = 0; j <= n; j++) {
        c[j] = j;
    }
    
    for (int i = 1; i <= m; i++) {
        vector<int> p = c;
        c[0] = i;
        for (int j = 1; j <= n; j++) {
            int a = p[j] + 1;           // удаление
            int d = c[j - 1] + 1;       // вставка
            int ch = p[j - 1];          // замена
            if (s1[j - 1] != s2[i - 1]) {
                ch++;
            }
            c[j] = min({a, d, ch});
        }
    }
    
    cout << c[n] << endl;
    return 0;
}

Как работает расстояние Левенштейна?

Расстояние Левенштейна (редакционное расстояние) — это минимальное количество операций (вставки, удаления, замены), необходимых для преобразования одной строки в другую.

Основная идея динамического программирования

Пусть dp[i][j] — минимальное расстояние между первыми i символами строки s1 и первыми j символами строки s2.

Рекуррентная формула:

Базовые случаи:

Оптимизация по памяти

Для вычисления текущей строки dp[i] нужны только предыдущая строка dp[i-1] и текущая dp[i]. Поэтому можно хранить всего два одномерных массива вместо полной матрицы n × m.

Временная сложность: O(n × m) — два вложенных цикла.

Пространственная сложность: O(min(n, m)) — оптимизированная версия с двумя массивами.

Пример работы

Рассмотрим строки:

s1 = "кот"

s2 = "кит"

Матрица dp (полная версия):

      ∅   к   и   т
   ∅  0   1   2   3
   к  1   0   1   2
   о  2   1   1   2
   т  3   2   2   1

Ответ: dp[3][3] = 1

Расстояние Левенштейна: 1 (замена 'о' на 'и')

Пошаговое объяснение

В более сложных примерах алгоритм может использовать комбинацию всех трёх операций для минимизации расстояния.

Попробовать алгоритм онлайн

Введите две строки и найдите расстояние Левенштейна:

Результат появится здесь...