Edit Distance
Ti vengono date due parole, word1 e word2. Una modifica cambia word1 in uno di tre modi: inserire una lettera in qualsiasi posizione, eliminare una lettera o sostituire una lettera con una diversa. Restituisci il numero minimo di modifiche necessarie per trasformare word1 in word2.
Funzione
- word1string
- la parola che modifichi
- word2string
- la parola raggiungere
- Restituisceinteger
- il minor numero di inserimenti, eliminazioni e sostituzioni che trasformano word1 in word2
Vincoli
1 ≤ word1.length ≤ 5001 ≤ word2.length ≤ 500- Entrambe le parole contengono solo lettere minuscole dell’alfabeto inglese.
Esempi
- Input
- word1 = "spot"word2 = "stop"
- Output
- 2
- Spiegazione
- Sostituisci la p con la t e la t con la p:
spotdiventastot, poistop. Una modifica non basta, perché le parole differiscono in due punti e un inserimento o un'eliminazione cambierebbe la lunghezza.
- Input
- word1 = "garden"word2 = "ardent"
- Output
- 2
- Spiegazione
- Elimina la g per ottenere
arden, poi inserisci t alla fine per ottenereardent. Sostituire una lettera alla volta costerebbe 6, perché le due parole differiscono in ogni posizione.
- Input
- word1 = "rain"word2 = "shine"
- Output
- 3
- Spiegazione
- Sostituisci r con s e a con h, poi inserisci e. Due modifiche non bastano: r e a non sono presenti in
shine, quindi ciascuna richiede una modifica che mantenga la lunghezza, e la parola deve comunque allungarsi di una lettera.
Per approfondire
Puoi anche restituire un elenco il più breve possibile delle modifiche, oltre al loro conteggio?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Guarda l’ultima lettera di ogni parola. Se sono uguali, devi modificarle? Se sono diverse, quali modifiche potrebbero far terminare le due parole allo stesso modo?
Ci sono tre possibilità per le diverse lettere finali: sostituirne una con l’altra, eliminare l’ultima lettera di
word1oppure inserire l’ultima lettera diword2. Ogni possibilità lascia lo stesso problema su prefissi più brevi, quindi scegli quella meno costosa e aggiungi uno.Memorizza la risposta per ogni coppia di lunghezze dei prefissi
(i, j)in una tabella. Un prefisso vuoto richiedeieliminazioni ojinserimenti, che riempiono la prima riga e la prima colonna. Riempi il resto riga per riga e leggi la risposta dall’ultima cella.
Soluzione
Le modifiche interagiscono: garden e ardent differiscono in tutte e sei le posizioni, eppure bastano due modifiche. Quindi guarda l'ultima lettera di ciascuna parola. O le due lettere coincidono, oppure una di tre modifiche le fa coincidere, e ogni scelta lascia lo stesso problema su prefissi più corti. Una tabella risolve una sola volta ogni coppia di prefissi.
Prova tutte e tre le modifiche con la ricorsione
Corretto, ma non termina sui test più grandi
Intuizione
Sia edits(i, j) il numero minimo di modifiche necessarie per trasformare il suffisso word1[i:] in word2[j:]. Se le prime lettere corrispondono, mantienile e sposta entrambi gli indici: spendere una modifica su una lettera corrispondente non è mai utile. Altrimenti, prendi 1 più il costo minore di tre chiamate: una sostituzione sposta entrambi gli indici, un’eliminazione di word1[i] sposta i e un inserimento di word2[j] sposta j. Quando una parola finisce, ogni lettera rimasta nell’altra costa una modifica.
Ogni mancata corrispondenza avvia tre chiamate: due parole di 15 lettere senza lettere in comune richiedono circa 6.7 × 10^10 chiamate. Eppure ci sono solo (n+1) × (m+1) coppie diverse (i, j), quindi quasi tutte le chiamate ripetono una chiamata precedente.
Algoritmo
- Se
isupera la fine diword1, restituiscim - j; sejsupera la fine diword2, restituiscin - i. - Se
word1[i] == word2[j], restituisciedits(i+1, j+1). - Altrimenti restituisci
1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)). - La risposta è
edits(0, 0).
def minDistance(word1, word2):
n, m = len(word1), len(word2)
def edits(i, j):
# Fewest edits to turn word1[i:] into word2[j:]
if i == n:
return m - j # insert the rest of word2
if j == m:
return n - i # delete the rest of word1
if word1[i] == word2[j]:
return edits(i + 1, j + 1)
return 1 + min(edits(i + 1, j + 1), # replace word1[i] with word2[j]
edits(i + 1, j), # delete word1[i]
edits(i, j + 1)) # insert word2[j]
return edits(0, 0)Completa una tabella dei prefissi
Intuizione
Sia dp[i][j] il numero minimo di modifiche necessarie per trasformare le prime i lettere di word1 nelle prime j lettere di word2. Se word1[i-1] è uguale a word2[j-1], copia il valore diagonale dp[i-1][j-1]. Altrimenti aggiungi 1 al vicino più conveniente: la diagonale corrisponde a una sostituzione, la cella sopra a un'eliminazione di word1[i-1], la cella a sinistra a un inserimento di word2[j-1]. La riga e la colonna di base non sono composte da zeri: per trasformare i lettere in niente servono i eliminazioni, quindi dp[i][0] = i, e analogamente dp[0][j] = j.
Per trasformare spot in stop, l'ultima riga è [4, 3, 2, 2, 2]. La cella finale confronta t con p; la sua diagonale (da spo a sto) vale 1 e gli altri vicini valgono 2, quindi la risposta è 1 + 1 = 2. Due parole di 500 lettere riempiono 2.5 × 10^5 celle, ciascuna in tempo costante.
Algoritmo
- Crea
dpcon(n+1) × (m+1)celle,dp[i][0] = iedp[0][j] = j. - Per
ida 1 anejda 1 am: seword1[i-1] == word2[j-1], impostadp[i][j] = dp[i-1][j-1]. - Altrimenti imposta
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). - Restituisci
dp[n][m].
def minDistance(word1, word2):
n, m = len(word1), len(word2)
# dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i # delete all i letters
for j in range(m + 1):
dp[0][j] = j # insert all j letters
for i in range(1, n + 1):
for j in range(1, m + 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 - 1], # replace
dp[i - 1][j], # delete word1[i-1]
dp[i][j - 1]) # insert word2[j-1]
return dp[n][m]Mantieni solo due righe
Intuizione
La riga i legge solo la riga i-1 e le proprie celle a sinistra, quindi bastano due array: prev per la riga completata e cur per la riga che stai riempiendo. La diagonale è prev[j-1], sopra c'è prev[j] e a sinistra cur[j-1]. La colonna base ora si trova nella prima voce di ogni riga, quindi imposta cur[0] = i prima di riempire la riga i.
Trasformare word2 in word1 richiede lo stesso numero di modifiche, poiché inserimenti ed eliminazioni si scambiano di ruolo. Scambia le parole in modo che le righe seguano quella più corta: min(n, m) + 1 numeri per riga invece di una tabella con un massimo di 251,001 celle, con lo stesso lavoro O(n × m).
Algoritmo
- Se
word2è più lungo diword1, scambiali. - Imposta
prev = [0, 1, ..., m]. - Per ogni
ida 1 an, impostacur[0] = ie riempicur[1..m]con la regola della tabella, leggendo la diagonale e il valore sopra dapreve il valore a sinistra dacur. Poi scambiaprevecur. - Restituisci
prev[m].
def minDistance(word1, word2):
if len(word2) > len(word1):
word1, word2 = word2, word1 # the rows run along the shorter word
m = len(word2)
# prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
prev = list(range(m + 1))
for i in range(1, len(word1) + 1):
cur = [i] + [0] * m # i letters into an empty prefix: delete them all
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], # replace
prev[j], # delete word1[i-1]
cur[j - 1]) # insert word2[j-1]
prev = cur
return prev[m]
Trappole e casi limite
- Riempire la riga 0 e la colonna 0 con zeri, come nella sottosequenza comune più lunga. Trasformare
abcin un prefisso vuoto costa 3 eliminazioni, non 0. - Dimenticare
cur[0] = inella versione a due righe. La prima voce mantiene un valore di due righe prima, e ogni cella successiva è errata. - Applicare un costo di modifica in caso di corrispondenza. Con
1 + min(...)per lettere uguali, trasformareainacosta 1. - Leggere il vicino a sinistra da
previnvece che dacur. A sinistra c'è l'inserimento diword2[j-1]nella riga corrente. - Ricorsione con memoizzazione in Python su parole di 500 lettere. Le chiamate raggiungono una profondità di 1000, superando il limite di ricorsione predefinito.
Domande frequenti3
Qual è la complessità temporale della distanza di modifica?
La soluzione con tabella riempie una cella per ogni coppia di prefissi in tempo costante: tempo O(n × m) per lunghezze n e m. Usa O(n × m) di memoria per la tabella completa, oppure O(min(n, m)) con due righe. La ricorsione semplice senza tabella è esponenziale.
La distanza di modifica è la stessa cosa della distanza di Levenshtein?
Questa versione è la distanza di Levenshtein: inserire, eliminare e sostituire hanno ciascuno un costo pari a uno. Distanza di modifica è il nome della famiglia. Solo inserimenti ed eliminazioni danno n + m - 2 × LCS, solo sostituzioni con lunghezze uguali danno la distanza di Hamming, e aggiungere lo scambio di due lettere adiacenti dà la versione di Damerau.
La distanza di modifica può essere risolta con un singolo array?
Sì. Riempi un array row sul posto, da sinistra a destra. Prima di sovrascrivere row[j], contiene ancora il valore della riga precedente, mentre row[j-1] contiene già il valore della riga corrente. Si perde solo la diagonale, quindi salva il vecchio row[j] in una variabile e usalo come diagonale per j + 1.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def minDistance(word1, word2):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
word1 = "spot" word2 = "stop"
Output atteso
2