Расстояние редактирования (Левенштейн)

Расстояние редактирования (Левенштейн)

Задача

Найти минимальное количество операций для преобразования строки word1 в word2.

Допустимые операции:

• Вставка символа
• Удаление символа
• Замена символа

Для примера edit_distance("horse", "ros") = 3:

1. horse → rorse (замена h на r)
2. rorse → rose (удаление r)
3. rose → ros (удаление e)

Решение 1: Dynamic Programming (O(m*n))

DP — оптимальный подход. Используем матрицу где dp[i][j] = расстояние между первыми i символами word1 и первыми j символами word2.

def editDistance(word1, word2):
    """
    Находит расстояние Левенштейна за O(m*n).
    
    DP подход:
    dp[i][j] = минимум операций для преобразования word1[:i] в word2[:j]
    
    Переходы:
    - Если word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]
    - Иначе: dp[i][j] = 1 + min(
        dp[i-1][j],      # удаление из word1
        dp[i][j-1],      # вставка в word1
        dp[i-1][j-1]     # замена
    )
    
    Временная сложность: O(m*n) где m=len(word1), n=len(word2)
    Пространственная сложность: O(m*n)
    """
    m, n = len(word1), len(word2)
    
    # Инициализируем DP таблицу
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Базовые случаи: преобразование в пустую строку
    for i in range(m + 1):
        dp[i][0] = i  # i удалений
    
    for j in range(n + 1):
        dp[0][j] = j  # j вставок
    
    # Заполняем таблицу
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                # Символы совпадают, операция не нужна
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # Берём минимум из трёх операций
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # удаление
                    dp[i][j - 1],      # вставка
                    dp[i - 1][j - 1]   # замена
                )
    
    return dp[m][n]

# Тестирование
print(editDistance("horse", "ros"))         # 3
print(editDistance("intention", "execution"))  # 5
print(editDistance("", "a"))               # 1
print(editDistance("a", ""))               # 1
print(editDistance("a", "a"))              # 0

Оптимизация пространства: O(min(m, n))

Так как нам нужны только предыдущие строки, можно использовать только две строки.

def editDistance_space_optimized(word1, word2):
    """
    Оптимизированная версия: O(min(m,n)) память.
    Идея: храним только предыдущую и текущую строки.
    """
    # Используем более короткую как word1
    if len(word1) > len(word2):
        word1, word2 = word2, word1
    
    m, n = len(word1), len(word2)
    
    # Две строки: предыдущая и текущая
    prev = list(range(n + 1))
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        curr[0] = i
        
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(
                    prev[j],      # удаление
                    curr[j - 1],  # вставка
                    prev[j - 1]   # замена
                )
        
        # Обновляем prev для следующей итерации
        prev, curr = curr, prev
    
    return prev[n]

print(editDistance_space_optimized("horse", "ros"))  # 3

Визуализация DP таблицы

Для word1 = "horse" и word2 = "ros":

      ""  r  o  s
  ""   0  1  2  3
  h    1  1  2  3
  o    2  2  1  2
  r    3  2  2  2
  s    4  3  3  2
  e    5  4  4  3

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

Объяснение:
- Заменяем h → r: dp[1][1] = 1
- Символ o совпадает: dp[2][2] = dp[1][1] = 1
- Удаляем r из "hor": dp[3][2] = 2
- Символ s совпадает: dp[4][3] = dp[3][2] = 2
- Удаляем e: dp[5][3] = dp[4][3] + 1 = 3

Решение 2: Мемоизация (Top-down DP)

Рекурсивный подход с кэшированием.

def editDistance_memo(word1, word2):
    """
    Мемоизированный подход: рекурсия с кэшем.
    
    Временная сложность: O(m*n)
    Пространственная сложность: O(m*n) для кэша + O(m+n) для стека
    """
    memo = {}
    
    def dp(i, j):
        # Базовые случаи
        if i == 0:
            return j
        if j == 0:
            return i
        
        # Проверяем кэш
        if (i, j) in memo:
            return memo[(i, j)]
        
        # Рекуррентное соотношение
        if word1[i - 1] == word2[j - 1]:
            result = dp(i - 1, j - 1)
        else:
            result = 1 + min(
                dp(i - 1, j),      # удаление
                dp(i, j - 1),      # вставка
                dp(i - 1, j - 1)   # замена
            )
        
        memo[(i, j)] = result
        return result
    
    return dp(len(word1), len(word2))

print(editDistance_memo("horse", "ros"))  # 3

Решение 3: Вывод последовательности операций

Не только расстояние, но и сами операции.

def editDistance_with_operations(word1, word2):
    """
    Возвращает расстояние И последовательность операций.
    """
    m, n = len(word1), len(word2)
    
    # Строим DP таблицу
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i - 1][j - 1]
                )
    
    # Восстанавливаем операции с конца
    operations = []
    i, j = m, n
    
    while i > 0 or j > 0:
        if i == 0:
            operations.append(f"Insert {word2[j - 1]}")
            j -= 1
        elif j == 0:
            operations.append(f"Delete {word1[i - 1]}")
            i -= 1
        elif word1[i - 1] == word2[j - 1]:
            operations.append(f"Match {word1[i - 1]}")
            i -= 1
            j -= 1
        elif dp[i - 1][j - 1] == dp[i][j] - 1:  # замена
            operations.append(f"Replace {word1[i - 1]} → {word2[j - 1]}")
            i -= 1
            j -= 1
        elif dp[i - 1][j] == dp[i][j] - 1:  # удаление
            operations.append(f"Delete {word1[i - 1]}")
            i -= 1
        else:  # вставка
            operations.append(f"Insert {word2[j - 1]}")
            j -= 1
    
    return dp[m][n], list(reversed(operations))

# Использование
dist, ops = editDistance_with_operations("horse", "ros")
print(f"Расстояние: {dist}")
for op in ops:
    print(f"  {op}")

# Вывод:
# Расстояние: 3
#   Replace h → r
#   Match o
#   Match r
#   Match s
#   Delete e

Трехмерная версия: LCS (Longest Common Subsequence)

Родственная задача на основе edit distance.

def longestCommonSubsequence(text1, text2):
    """
    Длина наибольшей общей подпоследовательности.
    Связана с edit_distance: LCS = (m + n - 2*LCS_length)/2
    """
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

print(longestCommonSubsequence("abcde", "ace"))  # 3 ("ace")

Сложность анализ

Практические применения

1. Проверка орфографии — расстояние до известных слов
2. Git diff — сравнение версий файлов
3. DNA sequencing — расстояние между ДНК последовательностями
4. Автодополнение — поиск близких совпадений
5. Spam detection — обнаружение похожих спам-сообщений

Пошаговый пример для интервью

# Словесно объяснить алгоритм:
# word1 = "horse", word2 = "ros"
# 
# i=1, j=1: h ≠ r → берём min(0+1, 1+1, 0+1) = 1
# i=1, j=2: h ≠ o → берём min(1+1, 1+1, 1+1) = 2
# ...
# i=5, j=3: e ≠ s → берём min(2+1, 3+1, 2+1) = 3
# Ответ: 3

Заключение

Edit Distance (Левенштейн) — классическая задача на динамическое программирование. Ключевые моменты:

1. DP таблица где dp[i][j] = расстояние между подстроками
2. Три операции: вставка, удаление, замена
3. Базовые случаи: пустые строки
4. Переход: совпадение или минимум из трёх операций
5. Можно оптимизировать память до O(n)

Часто встречается на интервью у крупных компаний (Google, Apple, Amazon, Meta).