Distanza di modifica (Levenshtein)
Derivi la ricorrenza della distanza di modifica per le operazioni di inserimento, eliminazione e sostituzione e compili la tabella DP per stringhe di lunghezza diversa
Distanza di modifica (Levenshtein) è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Il problema della distanza di modifica
La distanza di modifica (distanza di Levenshtein, LeetCode 72) chiede: qual è il numero minimo di operazioni di inserimento, cancellazione o sostituzione necessarie per trasformare una stringa in un’altra? Ad esempio, per trasformare 'horse' in 'ros': sostituire 'h'→'r' (horse→rorse), cancellare 'r' (rorse→rose), cancellare 'e' (rose→ros): 3 operazioni. La distanza di modifica è fondamentale per i correttori ortografici, l’allineamento del DNA e la corrispondenza approssimata.
# 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')Stato DP e ricorrenza
Definisca dp[i][j] come la distanza di modifica minima tra word1[:i] e word2[:j]. Se word1[i-1] == word2[j-1], non è necessaria alcuna operazione: dp[i][j] = dp[i-1][j-1]. Altrimenti, scelga il minimo tra tre operazioni: inserimento dp[i][j-1] + 1, cancellazione dp[i-1][j] + 1, sostituzione dp[i-1][j-1] + 1. Casi base: dp[i][0] = i (cancellare tutto word1) e dp[0][j] = j (inserire tutto 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')) # 5Comprendere le tre operazioni
Le tre operazioni corrispondono direttamente agli spostamenti nella tabella DP: Sostituzione dp[i-1][j-1]+1: si fanno corrispondere entrambi i caratteri, pagando però un costo. Cancellazione da word1 dp[i-1][j]+1: si rimuove un carattere da word1, spostandosi verso l’alto nella tabella. Inserimento in word1 dp[i][j-1]+1: si inserisce un carattere per farlo corrispondere a word2, spostandosi verso sinistra. Il minimo dei tre valori fornisce il percorso ottimale delle modifiche.
# 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)Ottimizzazione dello spazio fino a O(n)
La distanza di modifica necessita solo della riga corrente e di quella precedente. Usi un array 1D di dimensione n+1 e tenga separato il valore diagonal (dp[i-1][j-1]) prima di aggiornare ogni cella. Proceda da sinistra a destra: temp = dp[j] (vecchio valore = dp[i-1][j]), quindi aggiorni dp[j] usando dp[j] (cancellazione), dp[j-1] (inserimento) e diagonal (sostituzione).
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')) # 5Ricostruzione delle operazioni di modifica
Per ricostruire la sequenza effettiva delle modifiche, percorra a ritroso la tabella DP a partire da (m, n). In ogni cella: se word1[i-1] == word2[j-1], si sposti diagonalmente, senza eseguire operazioni. Altrimenti, individui quale dei tre vicini ha prodotto il minimo e registri l’operazione corrispondente. In questo modo otterrà lo script delle modifiche in ordine inverso; lo inverta per ottenere la risposta finale.
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)Verifica della distanza di una modifica
Un problema più semplice da colloquio è determinare se due stringhe sono a distanza di esattamente una modifica. È possibile risolverlo in O(n) senza usare la programmazione dinamica. Scorra entrambe le stringhe simultaneamente. In caso di mancata corrispondenza, provi tutte e tre le operazioni (saltare un carattere in s1, saltarne uno in s2 o saltarli entrambi) e verifichi se le parti rimanenti sono identiche. Se si verificano due mancate corrispondenze, restituisca False. Questo approccio greedy evita la DP completa O(mn) quando deve solo sapere se la distanza è ≤ 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')) # FalseConfronto tra distanza di modifica e LCS
La distanza di modifica, con tutte e tre le operazioni, e la LCS offrono due prospettive complementari sulla similarità tra stringhe. La distanza di modifica conta la differenza; la LCS conta la similarità. Quando sono consentiti solo inserimenti e cancellazioni, senza sostituzioni, la distanza di modifica = m + n - 2×LCS. Quando sono consentite le sostituzioni, la DP è leggermente diversa: la diagonale contribuisce con dp[i-1][j-1] in caso di corrispondenza, gratuitamente, oppure con dp[i-1][j-1]+1 in caso di sostituzione. Entrambi gli algoritmi richiedono O(mn) tempo.
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)Corrispondenza approssimata tra stringhe
La distanza di modifica è alla base della corrispondenza approssimata nelle applicazioni reali. Un correttore ortografico suggerisce correzioni che distano 1 o 2 modifiche dalla parola digitata. La difficoltà, quando si lavora su larga scala, consiste nell’evitare O(mn × dict_size) confronti. Tra le soluzioni vi sono i BK-trees (alberi metrici per la distanza di modifica), l’indicizzazione n-grammi e algoritmi di corrispondenza approssimata come Bitap. Comprendere la DP sottostante aiuta a ragionare sull’efficienza di questi strumenti di livello più alto.
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, morseDistanza di modifica pesata
In alcune applicazioni, operazioni diverse hanno costi diversi. Ad esempio, trasporre caratteri adiacenti, un errore di battitura comune, potrebbe costare meno di una sostituzione completa. La distanza di Damerau-Levenshtein aggiunge la trasposizione come quarta operazione. La DP si estende verificando anche dp[i-2][j-2]+1 quando word1[i-1]==word2[j-2] e word1[i-2]==word2[j-1]. Questo modello rappresenta in modo più accurato gli errori di battitura sulla tastiera.
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)Allineamento di sequenze di DNA
La bioinformatica utilizza varianti della distanza di modifica per l’allineamento di sequenze di DNA. L’algoritmo di Needleman-Wunsch è una DP per l’allineamento globale, strettamente correlata alla LCS e alla distanza di modifica, in cui una corrispondenza assegna +1, una mancata corrispondenza assegna -1 e un gap, ovvero un inserimento o una cancellazione, comporta una penalità. La variante Smith-Waterman esegue un allineamento locale, individuando la sottostringa con la migliore corrispondenza. Entrambi sono algoritmi DP O(mn) con la stessa struttura di riempimento della tabella.
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 scoreApproccio alla distanza di modifica durante un colloquio
Quando le viene chiesto di illustrare la distanza di modifica durante un colloquio: (1) confermi le operazioni consentite (inserimento/cancellazione/sostituzione); (2) definisca chiaramente lo stato DP; (3) scriva esplicitamente i tre casi e la ricorrenza; (4) indichi i casi base: dp[i][0]=i e dp[0][j]=j; (5) menzioni l’ottimizzazione dello spazio a O(n); (6) se il tempo lo consente, verifichi il procedimento con un piccolo esempio come 'cat'→'cut' (1 sostituzione). I limiti standard di complessità sono O(mn) di tempo e uno spazio che passa da O(mn) a 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', '')) # 3Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: edit distance dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost) with cost=0 on match else 1, i casi base dp[i][0]=i e dp[0][j]=j rappresentano la trasformazione da o verso una stringa vuota e l’ottimizzazione dello spazio a O(n) usa un array 1D scorrevole con una variabile diagonal. Nella prossima lezione applicheremo la stessa tecnica dell’array scorrevole per ridurre lo spazio delle tabelle DP 2D da O(mn) a O(min(m,n)).
Domande Frequenti
La lezione «Distanza di modifica (Levenshtein)» è gratuita?
Sì — il testo completo di «Distanza di modifica (Levenshtein)» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Distanza di modifica (Levenshtein)»?
Derivi la ricorrenza della distanza di modifica per le operazioni di inserimento, eliminazione e sostituzione e compili la tabella DP per stringhe di lunghezza diversa Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Distanza di modifica (Levenshtein)»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Percorsi unici e somma minima dei percorsi nelle griglie
- Sottosequenza comune più lunga
- Distanza di modifica (Levenshtein)
- Ottimizzazione dello spazio per la DP 2D