Edit-avstånd (Levenshtein)
Härled rekurrensen för edit-avstånd med infogning, borttagning och ersättning och fyll i DP-tabellen för strängpar av varierande längd.
Edit-avstånd (Levenshtein) är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Problemet med redigeringsavstånd
Redigeringsavstånd (Levenshtein-avstånd, LeetCode 72) frågar: hur många insättnings-, borttagnings- eller ersättningsoperationer krävs minst för att omvandla en sträng till en annan? För att till exempel omvandla 'horse' till 'ros' kan Ni ersätta 'h'→'r' (horse→rorse), ta bort 'r' (rorse→rose) och ta bort 'e' (rose→ros) — totalt 3 operationer. Redigeringsavstånd är grundläggande för stavningskontroller, DNA-justering och ungefärlig matchning.
# 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-tillstånd och rekurrens
Definiera dp[i][j] som det minsta redigeringsavståndet mellan word1[:i] och word2[:j]. Om word1[i-1] == word2[j-1] behövs ingen operation: dp[i][j] = dp[i-1][j-1]. Annars tar Ni minimum av tre operationer: infoga dp[i][j-1] + 1, ta bort dp[i-1][j] + 1 och ersätta dp[i-1][j-1] + 1. Basfall: dp[i][0] = i (ta bort hela word1) och dp[0][j] = j (infoga hela 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')) # 5Förstå de tre operationerna
De tre operationerna motsvarar direkt förflyttningar i DP-tabellen: Ersätt dp[i-1][j-1]+1 — vi matchade båda tecknen men betalade en kostnad på ett. Ta bort från word1 dp[i-1][j]+1 — ta bort ett tecken från word1 (gå uppåt i tabellen). Infoga i word1 dp[i][j-1]+1 — infoga ett tecken för att matcha word2 (gå åt vänster). Minimum av de tre ger den optimala redigeringsvägen.
# 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)Minnesoptimering till O(n)
Redigeringsavstånd behöver bara den aktuella raden och raden före. Använd en endimensionell array med storleken n+1 och håll reda på värdet diagonal (dp[i-1][j-1]) separat före varje celluppdatering. Bearbeta raden från vänster till höger: temp = dp[j] (gammalt värde = dp[i-1][j]), och uppdatera dp[j] med hjälp av dp[j] (borttagning), dp[j-1] (insättning) och diagonal (ersättning).
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Återskapa redigeringsoperationerna
För att återskapa den faktiska sekvensen av redigeringar går Ni bakåt genom DP-tabellen från (m, n). I varje cell gäller följande: om word1[i-1] == word2[j-1] går Ni diagonalt (ingen operation). Annars tar Ni reda på vilken av de tre grannarna som gav minimum och sparar motsvarande operation. Det här skapar redigeringsskriptet i omvänd ordning; vänd på det för att få det slutliga svaret.
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)Kontroll av ett redigeringssteg
Ett enklare intervjuproblem är att avgöra om två strängar skiljer sig åt med exakt ett redigeringssteg. Det kan lösas på O(n) utan DP. Gå igenom båda strängarna samtidigt. Vid en avvikelse provar Ni alla tre operationerna (hoppa över ett tecken i s1, hoppa över ett i s2 eller hoppa över ett i båda) och kontrollerar om de återstående delarna är identiska. Om två avvikelser uppstår returnerar Ni False. Den här giriga metoden undviker fullständig DP på O(mn) när Ni bara behöver veta om avståndet är ≤ 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')) # FalseJämförelse mellan redigeringsavstånd och LCS
Redigeringsavstånd (med alla tre operationerna) och LCS ger kompletterande perspektiv på stränglikhet. Redigeringsavstånd räknar skillnad, medan LCS räknar likhet. När endast insättningar och borttagningar tillåts (ingen ersättning) är redigeringsavstånd = m + n - 2×LCS. När ersättningar tillåts är DP:n något annorlunda: diagonalen bidrar med dp[i-1][j-1] vid träff (kostnadsfritt) eller dp[i-1][j-1]+1 vid ersättning. Båda algoritmerna körs på O(mn) tid.
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)Ungefärlig strängmatchning
Redigeringsavstånd används i praktiska tillämpningar av ungefärlig matchning. En stavningskontroll föreslår korrigeringar inom redigeringsavstånd 1 eller 2 från det inskrivna ordet. Utmaningen i stor skala är att undvika O(mn × ordboksstorlek) jämförelser. Lösningar omfattar BK-trees (ett metrisk träd för redigeringsavstånd), n-gramindexering och algoritmer för ungefärlig strängmatchning som Bitap. Genom att förstå den underliggande DP:n blir det lättare att bedöma effektiviteten hos dessa verktyg på högre nivå.
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, morseViktat redigeringsavstånd
I vissa tillämpningar har olika operationer olika kostnader. Att till exempel transponera intilliggande tecken (ett vanligt skrivfel) kan kosta mindre än en fullständig ersättning. Damerau-Levenshtein-avståndet lägger till transponering som en fjärde operation. DP:n utökas med att även kontrollera dp[i-2][j-2]+1 när word1[i-1]==word2[j-2] och word1[i-2]==word2[j-1]. Detta modellerar skrivfel på tangentbord mer korrekt.
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-sekvensjustering
Bioinformatik använder varianter av redigeringsavstånd för DNA-sekvensjustering. Algoritmen Needleman-Wunsch är en DP-algoritm för global justering som är nära besläktad med LCS och redigeringsavstånd, där en träff ger +1, en avvikelse ger -1 och ett gap (insättning/borttagning) ger en straffkostnad. Varianten Smith-Waterman utför lokal justering (hittar den delsträng som matchar bäst). Båda är DP-algoritmer på O(mn) med samma struktur för att fylla i tabellen.
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 scoreIntervjumetod för redigeringsavstånd
När Ni får en fråga om redigeringsavstånd under en intervju: (1) Bekräfta vilka operationer som tillåts (insättning/borttagning/ersättning). (2) Definiera DP-tillståndet tydligt. (3) Skriv uttryckligen ner de tre fallen och rekurrensen. (4) Ange basfallen: dp[i][0]=i och dp[0][j]=j. (5) Nämn minnesoptimeringen till O(n). (6) Om tiden tillåter, gå igenom ett litet exempel som 'cat'→'cut' (1 ersättning) för att validera lösningen. O(mn) tid och O(mn) → O(n) minne är de vanliga komplexitetsgränserna.
# 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', '')) # 3Snabb kontroll
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen lärde Ni er att: redigeringsavstånd dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost) med cost=0 vid träff och annars 1, basfallen dp[i][0]=i och dp[0][j]=j representerar omvandling till eller från en tom sträng, samt att minnesoptimeringen till O(n) använder en rullande endimensionell array med en diagonalvariabel. I nästa del använder vi samma trick med en rullande array för att reducera 2D-DP-tabeller från O(mn) till O(min(m,n)) minne.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Edit-avstånd (Levenshtein)” gratis?
Ja – hela texten till ”Edit-avstånd (Levenshtein)” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Edit-avstånd (Levenshtein)”?
Härled rekurrensen för edit-avstånd med infogning, borttagning och ersättning och fyll i DP-tabellen för strängpar av varierande längd. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Edit-avstånd (Levenshtein)”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Unika vägar och minsta vägsumma i rutnät
- Längsta gemensamma delsekvens
- Edit-avstånd (Levenshtein)
- Utrymmesoptimering för 2D-DP