Расстояние редактирования (Левенштейна)
Выводите рекуррентное соотношение для расстояния редактирования с операциями вставки, удаления и замены и заполняйте таблицу DP для строк разной длины
«Расстояние редактирования (Левенштейна)» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Задача о расстоянии редактирования
Расстояние редактирования (расстояние Левенштейна, LeetCode 72) — это минимальное число операций вставки, удаления или замены, необходимых для преобразования одной строки в другую. Например, чтобы преобразовать 'horse' в 'ros', нужно заменить 'h'→'r' (horse→rorse), удалить 'r' (rorse→rose) и удалить 'e' (rose→ros) — всего 3 операции. Расстояние редактирования лежит в основе средств проверки орфографии, выравнивания последовательностей DNA и нечёткого сопоставления.
# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)
# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose (delete r at index 1)
# 3. rose → ros (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')Состояние 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] + 1, удаление dp[i-1][j] + 1, замена dp[i-1][j-1] + 1. Базовые случаи: dp[i][0] = i (удалить все символы word1) и dp[0][j] = j (вставить все символы word2).
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
# Base cases
for i in range(m+1): dp[i][0] = i # delete all of word1
for j in range(n+1): dp[0][j] = j # insert all of word2
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] # no cost
else:
dp[i][j] = 1 + min(
dp[i][j-1], # insert
dp[i-1][j], # delete
dp[i-1][j-1] # replace
)
return dp[m][n]
print(edit_distance('horse', 'ros')) # 3
print(edit_distance('intention', 'execution')) # 5Понимание трёх операций
Три операции напрямую соответствуют переходам в таблице DP: Замена dp[i-1][j-1]+1 — мы сопоставили оба символа, заплатив одну операцию. Удаление из word1 dp[i-1][j]+1 — удалить символ из word1 (перейти вверх по таблице). Вставка в word1 dp[i][j-1]+1 — вставить символ, чтобы сопоставить его с word2 (перейти влево). Минимум из трёх значений задаёт оптимальный путь редактирования.
# Visualise the DP table for 'cat' → 'cut'
# dp[i][j] = min edits for word1[:i] vs word2[:j]
word1, word2 = 'cat', 'cut'
m, n = len(word1), len(word2)
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][j-1],dp[i-1][j],dp[i-1][j-1])
print(' ', ' '.join(' '+word2))
for i, row in enumerate(dp):
print((' ' if i==0 else word1[i-1]), row)Оптимизация памяти до O(n)
Для расстояния редактирования нужны только текущая и предыдущая строки. Используйте одномерный массив размера n+1 и отдельно отслеживайте значение diagonal (dp[i-1][j-1]) перед обновлением каждой ячейки. Обрабатывайте элементы слева направо: temp = dp[j] (старое значение = dp[i-1][j]), затем обновите dp[j], используя dp[j] (удаление), dp[j-1] (вставка) и diagonal (замена).
def edit_distance_1d(word1, word2):
m, n = len(word1), len(word2)
dp = list(range(n + 1)) # initial row: 0,1,2,...,n
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j] before overwrite
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], # delete
dp[j-1], # insert
diag) # replace
diag = temp
return dp[n]
print(edit_distance_1d('horse', 'ros')) # 3
print(edit_distance_1d('intention', 'execution')) # 5Восстановление операций редактирования
Чтобы восстановить фактическую последовательность изменений, выполните обратный проход по таблице DP, начиная с (m, n). В каждой ячейке: если word1[i-1] == word2[j-1], перейдите по диагонали без операции. В противном случае определите, какой из трёх соседей дал минимальное значение, и запишите соответствующую операцию. В результате сценарий изменений будет получен в обратном порядке; разверните его, чтобы получить окончательный ответ.
def edit_ops(word1, word2):
m, n = len(word1), len(word2)
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][j-1],dp[i-1][j],dp[i-1][j-1])
ops, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and word1[i-1]==word2[j-1]:
i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]<=dp[i-1][j] and dp[i][j-1]<=dp[i-1][j-1]):
ops.append(f'Insert {word2[j-1]} at pos {i}'); j-=1
elif i>0 and (j==0 or dp[i-1][j]<=dp[i][j-1] and dp[i-1][j]<=dp[i-1][j-1]):
ops.append(f'Delete {word1[i-1]} at pos {i-1}'); i-=1
else:
ops.append(f'Replace {word1[i-1]} with {word2[j-1]}'); i-=1; j-=1
return list(reversed(ops))
for op in edit_ops('horse', 'ros'): print(op)Проверка расстояния в одну операцию
Более простая задача для собеседования: отличаются ли две строки ровно одной операцией? Её можно решить за O(n) без DP. Одновременно просматривайте обе строки. При несовпадении попробуйте все три операции (пропустить символ в s1, пропустить символ в s2, пропустить оба символа) и проверьте, совпадают ли оставшиеся части. Если встречаются два несовпадения, верните False. Такой жадный подход позволяет не строить полную таблицу DP за O(mn), когда нужно лишь определить, не превышает ли расстояние 1.
def is_one_edit_distance(s, t):
m, n = len(s), len(t)
if abs(m - n) > 1: return False
if m > n: return is_one_edit_distance(t, s) # ensure m <= n
for i in range(m):
if s[i] != t[i]:
if m == n:
return s[i+1:] == t[i+1:] # replace
else:
return s[i:] == t[i+1:] # insert into s (delete from t)
return m + 1 == n # all matched, lengths differ by 1
print(is_one_edit_distance('ab', 'acb')) # True (insert c)
print(is_one_edit_distance('ab', 'ab')) # False (zero edits)
print(is_one_edit_distance('ab', 'abc')) # True (append c)
print(is_one_edit_distance('ab', 'xyz')) # FalseСравнение расстояния редактирования и LCS
Расстояние редактирования (со всеми тремя операциями) и LCS — это два взаимодополняющих взгляда на сходство строк. Расстояние редактирования измеряет различие, а LCS — сходство. Если разрешены только вставки и удаления (без замены), расстояние редактирования = m + n - 2×LCS. Если разрешены замены, DP немного отличается: при совпадении диагональный переход даёт dp[i-1][j-1] бесплатно, а при замене — dp[i-1][j-1]+1. Оба алгоритма выполняются за O(mn).
def lcs_len(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[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]
def edit_insert_delete_only(s1, s2):
return len(s1) + len(s2) - 2 * lcs_len(s1, s2)
print(edit_insert_delete_only('sea', 'eat')) # 2
print(edit_distance('sea', 'eat')) # 2 (same here: replace not needed)Нечёткое сопоставление строк
Расстояние редактирования используется в реальных системах для нечёткого сопоставления. Средство проверки орфографии предлагает исправления, находящиеся на расстоянии редактирования 1 или 2 от введённого слова. При работе с большими объёмами данных важно избежать O(mn × размера словаря) сравнений. Среди решений — деревья BK (метрическое дерево для расстояния редактирования), индексация n-грамм и алгоритмы приближённого сопоставления строк, например Битап. Понимание лежащего в основе DP помогает оценивать эффективность этих высокоуровневых инструментов.
def spell_suggest(typed, dictionary, max_dist=2):
'''Return words in dictionary within max_dist edits of typed.'''
suggestions = []
for word in dictionary:
if abs(len(typed) - len(word)) <= max_dist:
if edit_distance(typed, word) <= max_dist:
suggestions.append(word)
return suggestions
def edit_distance(w1, w2):
dp = list(range(len(w2)+1))
for i,c1 in enumerate(w1,1):
prev = i
for j,c2 in enumerate(w2,1):
temp = dp[j]
dp[j] = prev if c1==c2 else 1+min(dp[j],prev,dp[j-1])
prev = temp
return dp[len(w2)]
dictionary = ['horse', 'worse', 'house', 'morse', 'nurse']
print(spell_suggest('harse', dictionary)) # horse, worse, house, morseВзвешенное расстояние редактирования
В некоторых приложениях разные операции имеют разную стоимость. Например, перестановка соседних символов (распространённая опечатка) может стоить меньше, чем полная замена. Расстояние Дамерау — Левенштейна добавляет перестановку как четвёртую операцию. DP расширяется следующим образом: также проверьте dp[i-2][j-2]+1, если word1[i-1]==word2[j-2] и word1[i-2]==word2[j-1]. Это точнее моделирует опечатки при наборе текста.
def damerau_levenshtein(s, t):
m, n = len(s), len(t)
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):
cost = 0 if s[i-1]==t[j-1] else 1
dp[i][j] = min(
dp[i-1][j]+1, # delete
dp[i][j-1]+1, # insert
dp[i-1][j-1]+cost # replace
)
# Transposition
if i>1 and j>1 and s[i-1]==t[j-2] and s[i-2]==t[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2]+1)
return dp[m][n]
print(damerau_levenshtein('CA', 'ABC')) # 2
print(damerau_levenshtein('ab', 'ba')) # 1 (transposition)Выравнивание последовательностей DNA
В биоинформатике варианты расстояния редактирования используются для выравнивания последовательностей DNA. Алгоритм Нидлмана — Вунша — это DP для глобального выравнивания, тесно связанный с LCS и расстоянием редактирования: совпадение даёт +1, несовпадение — −1, а пропуск (вставка или удаление) — штраф. Вариант Смита — Уотермана выполняет локальное выравнивание, то есть находит наиболее подходящую подстроку. Оба алгоритма используют DP со сложностью O(mn) и одинаковой структурой заполнения таблицы.
def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-1):
m, n = len(seq1), len(seq2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i * gap
for j in range(n+1): dp[0][j] = j * gap
for i in range(1,m+1):
for j in range(1,n+1):
score = match if seq1[i-1]==seq2[j-1] else mismatch
dp[i][j] = max(
dp[i-1][j-1] + score, # align
dp[i-1][j] + gap, # gap in seq2
dp[i][j-1] + gap # gap in seq1
)
return dp[m][n]
print(needleman_wunsch('GATTACA', 'GCATGCU')) # alignment scoreПодход к расстоянию редактирования на собеседовании
Если на собеседовании Вас спрашивают о расстоянии редактирования: (1) Уточните разрешённые операции (вставка, удаление, замена). (2) Чётко определите состояние DP. (3) Явно запишите три случая и рекуррентное соотношение. (4) Назовите базовые случаи: dp[i][0]=i и dp[0][j]=j. (5) Упомяните оптимизацию памяти до O(n). (6) Если позволяет время, разберите небольшой пример, например 'cat'→'cut' (одна замена), чтобы проверить решение. Стандартные оценки сложности — время O(mn) и память O(mn) → O(n).
# Clean interview solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
# O(n) space with rolling row
dp = list(range(n + 1))
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], dp[j-1], diag)
diag = temp
return dp[n]
# Time: O(mn), Space: O(n)
print(min_distance('horse', 'ros')) # 3
print(min_distance('intention', 'execution')) # 5
print(min_distance('', 'abc')) # 3
print(min_distance('abc', '')) # 3Быстрая проверка
Проверьте, насколько хорошо Вы понимаете концепции курса «Структуры данных & алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали, что расстояние редактирования dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost), где cost=0 при совпадении и 1 в противном случае, базовые случаи dp[i][0]=i и dp[0][j]=j описывают преобразование в пустую строку и из неё, а оптимизация памяти до O(n) использует скользящий одномерный массив с переменной diagonal. Далее мы применим тот же приём со скользящим массивом, чтобы уменьшить таблицы двумерного DP с O(mn) до O(min(m,n)) памяти.
Часто задаваемые вопросы
Урок «Расстояние редактирования (Левенштейна)» бесплатный?
Да — полный текст урока «Расстояние редактирования (Левенштейна)» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Расстояние редактирования (Левенштейна)»?
Выводите рекуррентное соотношение для расстояния редактирования с операциями вставки, удаления и замены и заполняйте таблицу DP для строк разной длины Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Расстояние редактирования (Левенштейна)»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Уникальные пути и минимальная сумма пути на сетках
- Наибольшая общая подпоследовательность
- Расстояние редактирования (Левенштейна)
- Оптимизация памяти для двумерного DP