Odległość edycyjna (Levenshteina)
Wyprowadzą Państwo rekurencję odległości edycyjnej dla operacji wstawiania, usuwania i zastępowania oraz wypełnią tablicę DP dla par ciągów o różnej długości.
Odległość edycyjna (Levenshteina) to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Problem odległości edycyjnej
Odległość edycyjna (odległość Levenshteina, LeetCode 72) to minimalna liczba operacji wstawiania, usuwania lub zastępowania potrzebnych do przekształcenia jednego napisu w drugi. Na przykład, aby przekształcić 'horse' w 'ros': zastąp 'h'→'r' (horse→rorse), usuń 'r' (rorse→rose), usuń 'e' (rose→ros) — 3 operacje. Odległość edycyjna ma podstawowe znaczenie w programach sprawdzających pisownię, wyrównywaniu sekwencji DNA i przybliżonym dopasowywaniu.
# 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')Stan DP i rekurencja
Zdefiniuj dp[i][j] jako minimalną odległość edycyjną między word1[:i] a word2[:j]. Jeśli word1[i-1] == word2[j-1], żadna operacja nie jest potrzebna: dp[i][j] = dp[i-1][j-1]. W przeciwnym razie wybierz minimum z trzech operacji: wstawienie dp[i][j-1] + 1, usunięcie dp[i-1][j] + 1, zastąpienie dp[i-1][j-1] + 1. Przypadki bazowe: dp[i][0] = i (usunięcie całego word1) oraz dp[0][j] = j (wstawienie całego 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')) # 5Zrozumienie trzech operacji
Trzy operacje bezpośrednio odpowiadają ruchom w tabeli DP: Zastąpienie dp[i-1][j-1]+1 — dopasowaliśmy oba znaki, ale ponieśliśmy koszt jednej operacji. Usunięcie z word1 dp[i-1][j]+1 — usuwamy znak z word1 (przechodzimy w górę tabeli). Wstawienie do word1 dp[i][j-1]+1 — wstawiamy znak, aby dopasować word2 (przechodzimy w lewo). Minimum z tych trzech wartości wyznacza optymalną ścieżkę edycji.
# 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)Optymalizacja pamięci do O(n)
Odległość edycyjna wymaga tylko bieżącego i poprzedniego wiersza. Użyj tablicy 1D o rozmiarze n+1 i śledź osobno wartość diagonal (dp[i-1][j-1]) przed aktualizacją każdej komórki. Przetwarzaj komórki od lewej do prawej: temp = dp[j] (stara wartość = dp[i-1][j]), a następnie zaktualizuj dp[j] na podstawie dp[j] (usuwanie), dp[j-1] (wstawianie) i diagonal (zastępowanie).
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')) # 5Odtwarzanie operacji edycyjnych
Aby odtworzyć konkretny ciąg operacji edycyjnych, przejdź wstecz przez tabelę DP od (m, n). W każdej komórce: jeśli word1[i-1] == word2[j-1], przejdź po skosie (bez operacji). W przeciwnym razie sprawdź, który z trzech sąsiadów dał minimum, i zapisz odpowiadającą mu operację. W ten sposób otrzymasz skrypt edycji w odwrotnej kolejności; odwróć go, aby uzyskać ostateczną odpowiedź.
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)Sprawdzanie odległości edycyjnej równej 1
Prostszy problem rekrutacyjny: czy dwa napisy dzieli dokładnie jedna operacja edycyjna? Można go rozwiązać w czasie O(n), bez DP. Przechodź jednocześnie przez oba napisy. Po napotkaniu niezgodności wypróbuj wszystkie trzy operacje (pomiń znak w s1, pomiń znak w s2, pomiń oba znaki) i sprawdź, czy pozostałe fragmenty są identyczne. Jeśli wystąpią dwie niezgodności, zwróć False. To zachłanne podejście pozwala uniknąć pełnego DP w czasie O(mn), gdy trzeba tylko sprawdzić, czy odległość jest ≤ 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')) # FalsePorównanie odległości edycyjnej i LCS
Odległość edycyjna (z wszystkimi trzema operacjami) i LCS oferują uzupełniające się spojrzenia na podobieństwo napisów. Odległość edycyjna mierzy różnicę, a LCS mierzy podobieństwo. Gdy dozwolone są tylko wstawianie i usuwanie (bez zastępowania), odległość edycyjna = m + n - 2×LCS. Gdy dozwolone jest zastępowanie, DP wygląda nieco inaczej: wartość po przekątnej wynosi dp[i-1][j-1] dla zgodnych znaków (bez kosztu) albo dp[i-1][j-1]+1 dla zastąpienia. Oba algorytmy działają w czasie 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)Przybliżone dopasowywanie napisów
Odległość edycyjna jest podstawą rzeczywistych zastosowań przybliżonego dopasowywania. Program sprawdzający pisownię proponuje poprawki znajdujące się w odległości edycyjnej 1 lub 2 od wpisanego słowa. Wyzwaniem przy dużej skali jest uniknięcie O(mn × dict_size) porównań. Rozwiązania obejmują drzewa BK (drzewa metryczne dla odległości edycyjnej), indeksowanie n-gramów oraz algorytmy przybliżonego dopasowywania napisów, takie jak Bitap. Zrozumienie podstawowego DP pomaga oceniać wydajność tych narzędzi wyższego poziomu.
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, morseWażona odległość edycyjna
W niektórych zastosowaniach różne operacje mają różne koszty. Na przykład transponowanie sąsiednich znaków (częsta literówka) może kosztować mniej niż pełne zastąpienie. Odległość Damerau-Levenshteina dodaje transponowanie jako czwartą operację. DP rozszerza się tak, aby dodatkowo sprawdzać dp[i-2][j-2]+1, gdy word1[i-1]==word2[j-2] oraz word1[i-2]==word2[j-1]. Lepiej odwzorowuje to literówki popełniane podczas pisania na klawiaturze.
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)Wyrównywanie sekwencji DNA
Bioinformatyka wykorzystuje warianty odległości edycyjnej do wyrównywania sekwencji DNA. Algorytm Needleman-Wunsch to algorytm globalnego wyrównywania oparty na DP, blisko spokrewniony z LCS i odległością edycyjną, w którym zgodność daje +1, niezgodność daje -1, a luka (wstawienie/usunięcie) wiąże się z karą. Wariant Smith-Waterman wykonuje wyrównywanie lokalne (znajduje najlepiej dopasowany podłańcuch). Oba algorytmy są algorytmami DP o czasie O(mn), wykorzystującymi tę samą strukturę wypełniania tabeli.
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 scorePodejście do odległości edycyjnej na rozmowie rekrutacyjnej
Gdy podczas rozmowy rekrutacyjnej pojawi się temat odległości edycyjnej: (1) Potwierdź dozwolone operacje (wstawianie/usuwanie/zastępowanie). (2) Jasno zdefiniuj stan DP. (3) Zapisz wyraźnie trzy przypadki i rekurencję. (4) Podaj przypadki bazowe: dp[i][0]=i oraz dp[0][j]=j. (5) Wspomnij o optymalizacji pamięci do O(n). (6) Jeśli starczy czasu, prześledź mały przykład, taki jak 'cat'→'cut' (1 zastąpienie), aby sprawdzić rozwiązanie. Standardowe ograniczenia złożoności to czas O(mn) oraz pamięć O(mn), którą można zmniejszyć do 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', '')) # 3Szybki test
Sprawdź swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyłeś się, że: odległość edycyjna dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost) z cost=0 dla zgodnych znaków, a w przeciwnym razie 1, przypadki bazowe dp[i][0]=i i dp[0][j]=j oznaczają przekształcanie do pustego napisu lub z niego oraz optymalizacja pamięci do O(n) wykorzystuje kroczącą tablicę 1D ze zmienną diagonal. Następnie zastosujemy tę samą sztuczkę z tablicą kroczącą, aby zmniejszyć pamięć zajmowaną przez tabele DP 2D z O(mn) do O(min(m,n)).
Często zadawane pytania
Czy lekcja „Odległość edycyjna (Levenshteina)” jest bezpłatna?
Tak — pełny tekst „Odległość edycyjna (Levenshteina)” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Odległość edycyjna (Levenshteina)”?
Wyprowadzą Państwo rekurencję odległości edycyjnej dla operacji wstawiania, usuwania i zastępowania oraz wypełnią tablicę DP dla par ciągów o różnej długości. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Odległość edycyjna (Levenshteina)”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Unikalne ścieżki i minimalna suma ścieżki na siatkach
- Najdłuższy wspólny podciąg
- Odległość edycyjna (Levenshteina)
- Optymalizacja pamięci dla dwuwymiarowego DP