Edit Distance
Du erhältst zwei Wörter, word1 und word2. Eine Bearbeitung ändert word1 auf eine von drei Arten: Füge irgendwo einen Buchstaben ein, lösche einen Buchstaben oder ersetze einen Buchstaben durch einen anderen. Gib die minimale Anzahl an Bearbeitungen zurück, die erforderlich ist, um word1 in word2 umzuwandeln.
Funktion
- word1string
- das Wort, das du bearbeitest
- word2string
- das Wort erreichen
- Gibt zurückinteger
- die wenigsten Einfügungen, Löschungen und Ersetzungen, die word1 in word2 umwandeln
Einschränkungen
1 ≤ word1.length ≤ 5001 ≤ word2.length ≤ 500- Beide Wörter enthalten ausschließlich englische Kleinbuchstaben.
Beispiele
- Eingabe
- word1 = "spot"word2 = "stop"
- Ausgabe
- 2
- Erklärung
- Ersetze das p durch t und das t durch p:
spotwird zustot, dannstop. Eine Änderung reicht nicht aus, weil sich die Wörter an zwei Stellen unterscheiden und ein Einfügen oder Löschen die Länge verändern würde.
- Eingabe
- word1 = "garden"word2 = "ardent"
- Ausgabe
- 2
- Erklärung
- Entferne das g, um
ardenzu erhalten, und füge dann am Ende ein t ein, umardentzu erhalten. Buchstabe für Buchstabe zu ersetzen würde 6 kosten, da sich die beiden Wörter an jeder Position unterscheiden.
- Eingabe
- word1 = "rain"word2 = "shine"
- Ausgabe
- 3
- Erklärung
- Ersetze r durch s und a durch h, dann füge e ein. Zwei Bearbeitungen reichen nicht: r und a kommen in
shinenicht vor, daher ist für jedes eine Bearbeitung erforderlich, die die Länge beibehält, und das Wort muss trotzdem um eins wachsen.
Weiterführende Frage
Kannst du neben der Anzahl auch eine kürzeste Liste der Änderungen zurückgeben?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Sieh dir den letzten Buchstaben jedes Wortes an. Wenn sie gleich sind, musst du sie verändern? Wenn sie unterschiedlich sind, welche Änderungen könnten dafür sorgen, dass die beiden Wörter gleich enden?
Für unterschiedliche letzte Buchstaben gibt es drei Möglichkeiten: einen durch den anderen ersetzen, den letzten Buchstaben von
word1löschen oder den letzten Buchstaben vonword2einfügen. Jede Möglichkeit führt zum gleichen Problem mit kürzeren Präfixen. Nimm also die kostengünstigste Möglichkeit und addiere eins.Speichere die Antwort für jedes Paar von Präfixlängen
(i, j)in einer Tabelle. Ein leeres Präfix kostetiLöschungen oderjEinfügungen, womit die erste Zeile und die erste Spalte gefüllt werden. Fülle den Rest zeilenweise aus und lies die Antwort aus der letzten Zelle ab.
Lösung
Änderungen greifen ineinander: garden und ardent unterscheiden sich an allen sechs Positionen, doch zwei Änderungen genügen. Betrachte also den letzten Buchstaben jedes Wortes. Entweder stimmen die beiden überein, oder eine von drei Änderungen bringt sie zur Übereinstimmung, und jede Wahl lässt dasselbe Problem mit kürzeren Präfixen zurück. Eine Tabelle löst jedes Präfixpaar genau einmal.
Probiere alle drei Änderungen mit Rekursion aus
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Sei edits(i, j) die geringste Anzahl von Änderungen, mit der sich das Suffix word1[i:] in word2[j:] umwandeln lässt. Stimmen die ersten Buchstaben überein, behalte sie bei und erhöhe beide Indizes: Eine Änderung an einem übereinstimmenden Buchstaben hilft nie. Andernfalls nimm 1 plus das Minimum aus drei Aufrufen: Beim Ersetzen werden beide Indizes erhöht, beim Löschen von word1[i] wird i erhöht und beim Einfügen von word2[j] wird j erhöht. Wenn ein Wort aufgebraucht ist, kostet jeder im anderen verbleibende Buchstabe eine Änderung.
Jede Abweichung startet drei Aufrufe: Bei zwei 15 Buchstaben langen Wörtern, die keinen Buchstaben gemeinsam haben, sind es etwa 6.7 × 10^10 Aufrufe. Es gibt jedoch nur (n+1) × (m+1) verschiedene Paare (i, j), daher wiederholt fast jeder Aufruf einen früheren.
Algorithmus
- Wenn
ihinter dem Ende vonword1liegt, gibm - jzurück; wennjhinter dem Ende vonword2liegt, gibn - izurück. - Wenn
word1[i] == word2[j]gilt, gibedits(i+1, j+1)zurück. - Andernfalls gib
1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1))zurück. - Die Antwort ist
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)Fülle eine Präfixtabelle aus
Idee
Sei dp[i][j] die kleinste Anzahl an Bearbeitungsschritten, um die ersten i Buchstaben von word1 in die ersten j Buchstaben von word2 umzuwandeln. Wenn word1[i-1] gleich word2[j-1] ist, übernimm den diagonalen Wert dp[i-1][j-1]. Andernfalls addiere 1 zum kleinsten Wert der Nachbarzellen: Die diagonale Zelle steht für ein Ersetzen, die Zelle darüber für das Löschen von word1[i-1], die Zelle links für das Einfügen von word2[j-1]. Die Basiszeile und -spalte sind nicht mit Nullen gefüllt: Für i Buchstaben braucht man zum Umwandeln in nichts i Löschvorgänge, also dp[i][0] = i, und entsprechend gilt dp[0][j] = j.
Für spot in stop lautet die letzte Zeile [4, 3, 2, 2, 2]. Die letzte Zelle vergleicht t mit p; ihr diagonaler Wert (spo in sto) ist 1 und ihre anderen Nachbarwerte sind 2, daher ist die Antwort 1 + 1 = 2. Zwei Wörter mit je 500 Buchstaben füllen 2.5 × 10^5 Zellen, jede in konstanter Zeit.
Algorithmus
- Erstelle
dpmit(n+1) × (m+1)Zellen,dp[i][0] = iunddp[0][j] = j. - Für
ivon 1 bisnundjvon 1 bism: Wennword1[i-1] == word2[j-1], setzedp[i][j] = dp[i-1][j-1]. - Andernfalls setze
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). - Gib
dp[n][m]zurück.
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]Behalte nur zwei Zeilen
Idee
Zeile i liest nur Zeile i-1 und ihre eigenen Zellen links davon, daher reichen zwei Arrays aus: prev für die fertige Zeile und cur für die Zeile, die du gerade ausfüllst. Die Diagonale ist prev[j-1], darüber liegt prev[j] und links davon cur[j-1]. Die Basisspalte befindet sich jetzt im ersten Eintrag jeder Zeile. Setze daher cur[0] = i, bevor du Zeile i ausfüllst.
word2 in word1 umzuwandeln erfordert dieselbe Anzahl an Bearbeitungsschritten, da sich Einfüge- und Löschvorgänge gegenseitig ersetzen. Vertausche die Wörter, sodass die Zeilen entlang des kürzeren Wortes verlaufen: min(n, m) + 1 Zahlen pro Zeile statt einer Tabelle mit bis zu 251,001 Zellen, bei gleichem Aufwand von O(n × m).
Algorithmus
- Wenn
word2länger alsword1ist, vertausche sie. - Setze
prev = [0, 1, ..., m]. - Setze für jedes
ivon 1 bisncur[0] = iund füllecur[1..m]nach der Tabellenregel aus. Lies dabei die Diagonale und den Wert darüber ausprevund den Wert links davon auscur. Vertausche dannprevundcur. - Gib
prev[m]zurück.
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]
Stolperfallen und Grenzfälle
- Zeile 0 und Spalte 0 mit Nullen füllen, wie bei der längsten gemeinsamen Teilfolge.
abcin ein leeres Präfix umzuwandeln kostet 3 Löschungen, nicht 0. cur[0] = iin der Zwei-Zeilen-Version vergessen. Der erste Eintrag behält einen Wert von zwei Zeilen zuvor, und alle Zellen danach sind falsch.- Bei einer Übereinstimmung eine Bearbeitung berechnen. Mit
1 + min(...)bei gleichen Buchstaben kostet es 1,ainaumzuwandeln. - Den linken Nachbarn aus
prevstatt auscurlesen. Links steht das Einfügen vonword2[j-1]in der aktuellen Zeile. - Memoisierte Rekursion in Python bei Wörtern mit 500 Buchstaben verwenden. Die Aufrufe gehen bis zu einer Tiefe von 1000, über das standardmäßige Rekursionslimit hinaus.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität der Editierdistanz?
Die Tabellenlösung füllt eine Zelle pro Präfixpaar in konstanter Zeit: O(n × m) Zeit für die Längen n und m. Sie benötigt O(n × m) Speicher für die vollständige Tabelle oder O(min(n, m)) mit zwei Zeilen. Einfache Rekursion ohne Tabelle ist exponentiell.
Ist die Editierdistanz dasselbe wie die Levenshtein-Distanz?
Diese Version ist die Levenshtein-Distanz: Einfügen, Löschen und Ersetzen kosten jeweils eins. Edit-Distanz ist der Oberbegriff. Nur Einfügen und Löschen ergibt n + m - 2 × LCS, nur Ersetzen bei gleichen Längen ergibt die Hamming-Distanz, und das Hinzufügen des Vertauschens zweier benachbarter Buchstaben ergibt die Damerau-Version.
Kann die Editierdistanz mit einem einzigen Array berechnet werden?
Ja. Fülle ein Array row direkt von links nach rechts. Bevor du row[j] überschreibst, enthält es noch den Wert aus der Zeile darüber, und row[j-1] enthält bereits den Wert der aktuellen Zeile. Nur die Diagonale geht verloren, also speichere den alten Wert von row[j] in einer Variablen und verwende ihn als Diagonale für j + 1.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def minDistance(word1, word2):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
word1 = "spot" word2 = "stop"
Erwartete Ausgabe
2