Edit Distance

Q: Wie hoch ist die Zeitkomplexität der Editierdistanz?

Die Tabellenlösung benötigt O(n × m) Zeit, wobei n und m die beiden Längen sind, da sie mit konstantem Aufwand eine Zelle pro Paar von Präfixen füllt. Für die vollständige Tabelle benötigt sie O(n × m) Speicher oder mit zwei Zeilen O(min(n, m)) . Einfache Rekursion ohne Tabelle hat exponentielle Laufzeit.

Q: Wie erhältst du die Liste der Änderungen und nicht nur die Anzahl?

Behalte die vollständige Tabelle und gehe von dp[n][m] zurück. Wenn die Buchstaben übereinstimmen, gehe diagonal weiter, ohne eine Bearbeitung vorzunehmen. Andernfalls gehe zu dem benachbarten Feld, dessen Wert um eins kleiner ist: diagonal bedeutet Ersetzen, nach oben bedeutet Löschen, nach links bedeutet Einfügen. Höre bei dp[0][0] auf und lies die Bearbeitungen in umgekehrter Reihenfolge. Mit der Version mit zwei Zeilen geht das nicht allein, weil sie die vorherigen Zeilen verworfen hat.

Q: Kann die Editierdistanz mit einem einzigen Array gelöst werden?

Ja. Fülle ein Array row an Ort und Stelle von links nach rechts. Bevor du row[j] überschreibst, enthält es noch den Wert aus der vorherigen Zeile, und row[j-1] enthält bereits den Wert der aktuellen Zeile. Der einzige Wert, den du verlierst, ist der diagonale Wert. Bewahre ihn deshalb in einer Variable auf: Speichere den alten Wert von row[j] , bevor du ihn überschreibst, und verwende ihn als Diagonalwert für j + 1 .

SchwerDynamische Programmierung

+10

Du erhältst zwei Wörter, word1 und word2. Eine Änderung verändert word1 auf eine von drei Arten: einen Buchstaben an beliebiger Stelle einfügen, einen Buchstaben löschen oder einen Buchstaben durch einen anderen ersetzen. Gib die geringste Anzahl an Änderungen zurück, mit der sich word1 in word2 umwandeln lässt.

Funktion

minDistance(word1: string, word2: string) → integer

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 ≤ 500
1 ≤ 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: spot wird zu stot, dann zu stop. 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: Lösche das g, um arden zu erhalten, und füge dann am Ende ein t ein, um ardent zu 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, um shin zu erhalten, und füge dann e ein. Mit zwei Änderungen geht das nicht: r und a kommen in shine nicht vor, daher kostet jedes von ihnen eine Änderung, durch die das Wort nicht länger wird, und das Wort muss trotzdem um einen Buchstaben wachsen.

+21 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du auch eine kürzeste Liste der Änderungen zurückgeben und nicht nur angeben, wie viele es sind?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Änderungen beeinflussen sich gegenseitig, deshalb kannst du die Wörter nicht Position für Position korrigieren: garden und ardent unterscheiden sich an allen sechs Positionen, doch zwei Änderungen reichen aus, sobald das g gelöscht wird und alles nach links rückt. Der entscheidende Gedanke ist, nur den letzten Buchstaben jedes Wortes zu betrachten. Entweder stimmen die beiden Buchstaben bereits überein, oder eine von genau drei Änderungen bringt sie zur Übereinstimmung, und jede Wahl führt zum gleichen Problem bei kürzeren Präfixen. Eine Tabelle mit (n+1) × (m+1) Antworten löst jedes Paar von Präfixen auf einmal, und zwei Zeilen davon reichen aus.

Probiere alle drei Änderungen mit Rekursion aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Sei edits(i, j) die kleinste Anzahl von Bearbeitungsschritten, mit der sich das Suffix word1[i:] in word2[j:] umwandeln lässt. Betrachte die ersten Buchstaben der beiden Suffixe. Sind sie gleich, behalte sie bei und rücke beide Indizes weiter: Ein übereinstimmender Buchstabe muss nie bearbeitet werden, und jeder Plan, der einen Bearbeitungsschritt dafür aufwendet, lässt sich in einen Plan umwandeln, der ihn beibehält, ohne länger zu werden.

Unterscheiden sie sich, muss ein Bearbeitungsschritt word1[i] behandeln oder word2[j] erzeugen, und es gibt genau drei Möglichkeiten. Ersetze word1[i] durch word2[j] und rücke beide Indizes weiter: edits(i+1, j+1). Lösche word1[i] und rücke nur i weiter: edits(i+1, j). Füge word2[j] davor ein und rücke nur j weiter: edits(i, j+1). Die Antwort ist 1 plus die günstigste der drei Möglichkeiten. Wenn word1 aufgebraucht ist, füge den Rest von word2 ein; das kostet m - j. Wenn word2 aufgebraucht ist, lösche den Rest von word1; das kostet n - i.

Das Verfahren ist langsam, weil bei jeder Abweichung drei Aufrufe gestartet werden. Bei zwei Wörtern mit jeweils 15 Buchstaben, die keinen Buchstaben gemeinsam haben, sind das etwa 6.7 × 10^10 Aufrufe, und die großen Tests haben jeweils 500 Buchstaben. Es gibt jedoch nur (n+1) × (m+1) verschiedene Paare (i, j), sodass fast jeder Aufruf einen bereits zuvor ausgeführten wiederholt.

Algorithmus

Schreibe edits(i, j) für die Suffixe, die bei i und j beginnen.
Wenn i hinter dem Ende von word1 liegt, gib m - j zurück; wenn j hinter dem Ende von word2 liegt, gib n - i zurück.
Wenn word1[i] == word2[j] gilt, gib edits(i+1, j+1) zurück.
Andernfalls gib 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)) für Ersetzen, Löschen und Einfügen 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 Tabelle mit Präfixen aus

Idee

Zustand. Sei dp[i][j] die minimale Anzahl an Bearbeitungen, um die ersten i Buchstaben von word1 in die ersten j Buchstaben von word2 umzuwandeln. Index 0 steht für ein leeres Präfix.

Übergänge. Vergleiche die letzten Buchstaben der beiden Präfixe, word1[i-1] und word2[j-1]. Sind sie gleich, behalte sie bei: dp[i][j] = dp[i-1][j-1], die Zelle diagonal oben links. Andernfalls ist eine Bearbeitung nötig; nimm den kleinsten Wert von drei benachbarten Zellen. Die diagonale Zelle dp[i-1][j-1] bedeutet, word1[i-1] durch word2[j-1] zu ersetzen. Die Zelle darüber, dp[i-1][j], bedeutet, word1[i-1] zu löschen. Die Zelle links davon, dp[i][j-1], bedeutet, word2[j-1] am Ende einzufügen.

Basiszeile und -spalte. Anders als bei vielen Tabellenproblemen enthalten sie keine Nullen. Um i Buchstaben in ein leeres Präfix umzuwandeln, sind i Löschvorgänge nötig, also dp[i][0] = i. Um j Buchstaben aus dem Nichts aufzubauen, sind j Einfügevorgänge nötig, also dp[0][j] = j. Jede Zelle greift auf die Zelle darüber, die links davon und die diagonale Zelle zu. Füllt man die Tabelle also zeilenweise von links nach rechts, sind diese Werte bereits vorhanden. Die Antwort ist dp[n][m].

Hier ist die Tabelle für spot zu stop, mit Spalten für die Präfixe "", s, st, sto, stop. Die Zeile "" ist [0, 1, 2, 3, 4], die Zeile s ist [1, 0, 1, 2, 3], die Zeile sp ist [2, 1, 1, 2, 2], die Zeile spo ist [3, 2, 2, 1, 2] und die Zeile spot ist [4, 3, 2, 2, 2]. Sieh dir einige Zellen an. s stimmt mit s überein, also wird der diagonale Wert 0 übernommen. sp stimmt nicht mit st überein: Die Nachbarwerte sind diagonal 0, darüber 1 und links 1. Der Wert ist also 1 + 0 = 1, eine Ersetzung. spo stimmt bei o mit sto überein und übernimmt den Wert 1. In der letzten Zelle werden bei spot und stop t und p verglichen: Die Nachbarwerte sind 1, 2 und 2, also ist die Antwort 1 + 1 = 2.

Die Tabelle enthält (n+1) × (m+1) Zellen, für die jeweils ein konstanter Arbeitsaufwand anfällt, also etwa 2.5 × 10^5 Schritte für zwei Wörter mit jeweils 500 Buchstaben. Eine Rekursion mit Memoisierung füllt dieselben Zellen, kann aber bis zu n + m Aufrufe tief rekursiv sein und damit Pythons Standardgrenze von 1000 überschreiten.

Algorithmus

Erstelle eine Tabelle dp mit (n+1) × (m+1) Zellen.
Setze dp[i][0] = i für jedes i und dp[0][j] = j für jedes j.
Gehe für i von 1 bis n und für j von 1 bis m. Wenn word1[i-1] == word2[j-1], setze dp[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. Sobald eine Zeile fertig ist, werden die darüberliegenden Zeilen nicht mehr gelesen. Verwende zwei Arrays: prev für die fertige Zeile und cur für die Zeile, die du gerade ausfüllst, und tausche sie nach jeder Zeile. Die Übergänge ändern sich nicht: Die Diagonale ist prev[j-1], oben ist prev[j] und links ist cur[j-1].

Die Basisspalte verschwindet nicht. Sie befindet sich jetzt im ersten Eintrag jeder Zeile. Setze daher cur[0] = i, bevor du Zeile i ausfüllst. Zeile 0 beginnt als [0, 1, 2, ..., m], die Basiszeile.

Es kostet gleich viele Bearbeitungsschritte, word2 in word1 umzuwandeln, denn jedes Einfügen wird zu einem Löschen und jedes Löschen zu einem Einfügen. Du kannst also die Wörter vertauschen und die Zeilen entlang des kürzeren Wortes laufen lassen. Jede Zeile enthält dann min(n, m) + 1 Zahlen statt einer Tabelle mit bis zu 251,001 Zellen, und der Aufwand bleibt O(n × m).

Algorithmus

Wenn word2 länger als word1 ist, vertausche sie.
Setze prev = [0, 1, ..., m], wobei m die kürzere Länge ist.
Setze für jedes i von 1 bis n cur[0] = i und fülle dann cur[1..m] nach derselben Regel, wobei du die Diagonale und den Wert darüber aus prev und den Wert links davon aus cur liest.
Vertausche prev und cur.
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

Die Rekurrenz ist kurz, daher liegen die meisten Fehler in den Basisfällen oder darin, welcher Nachbar gelesen wird.

Zeile 0 und Spalte 0 mit Nullen füllen, wie bei der längsten gemeinsamen Teilsequenz. abc in ein leeres Präfix umzuwandeln kostet 3 Löschungen, nicht 0, also muss dp[i][0] i und dp[0][j] j sein.
In der Version mit zwei Zeilen cur[0] = i vergessen. Der erste Eintrag behält einen Wert von zwei Zeilen zuvor, und jede Zelle danach ist falsch.
Bei einer Übereinstimmung eine Bearbeitung berechnen. dp[i][j] = 1 + min(...) bei gleichen Buchstaben lässt a zu a werden und kostet 1. Bei einer Übereinstimmung kopierst du den diagonalen Wert.
Den linken Nachbarn aus prev statt aus cur lesen. Links liegt in der aktuellen Zeile: Es ist das Einfügen von word2[j-1], nachdem word1[:i] bereits in word2[:j-1] umgewandelt wurde.
Position für Position vergleichen. Die Stellen zu zählen, an denen sich die Wörter unterscheiden, ignoriert Einfügungen und Löschungen: Für garden und ardent ergibt das 6, obwohl die Antwort 2 ist.
Rekursion für Wörter mit 500 Buchstaben mit Memoisierung verwenden. Die Aufruftiefe erreicht 1000, was Pythons Standardgrenzwert ist.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität der Editierdistanz?

Die Tabellenlösung benötigt O(n × m) Zeit, wobei n und m die beiden Längen sind, da sie mit konstantem Aufwand eine Zelle pro Paar von Präfixen füllt. Für die vollständige Tabelle benötigt sie O(n × m) Speicher oder mit zwei Zeilen O(min(n, m)). Einfache Rekursion ohne Tabelle hat exponentielle Laufzeit.

Ist die Editierdistanz dasselbe wie die Levenshtein-Distanz?

Ja, diese Version ist die Levenshtein-Distanz: Einfügen, Löschen und Ersetzen kosten jeweils eins. Editierdistanz ist der Oberbegriff. Andere Varianten erlauben weniger oder mehr Bearbeitungen: Nur Einfügen und Löschen ergibt n + m - 2 × LCS, nur Ersetzen bei gleicher Länge ergibt die Hamming-Distanz, und das Hinzufügen des Vertauschens zweier benachbarter Buchstaben ergibt die Damerau-Variante.

Wie erhältst du die Liste der Änderungen und nicht nur die Anzahl?

Behalte die vollständige Tabelle und gehe von dp[n][m] zurück. Wenn die Buchstaben übereinstimmen, gehe diagonal weiter, ohne eine Bearbeitung vorzunehmen. Andernfalls gehe zu dem benachbarten Feld, dessen Wert um eins kleiner ist: diagonal bedeutet Ersetzen, nach oben bedeutet Löschen, nach links bedeutet Einfügen. Höre bei dp[0][0] auf und lies die Bearbeitungen in umgekehrter Reihenfolge. Mit der Version mit zwei Zeilen geht das nicht allein, weil sie die vorherigen Zeilen verworfen hat.

Kann die Editierdistanz mit einem einzigen Array gelöst werden?

Ja. Fülle ein Array row an Ort und Stelle von links nach rechts. Bevor du row[j] überschreibst, enthält es noch den Wert aus der vorherigen Zeile, und row[j-1] enthält bereits den Wert der aktuellen Zeile. Der einzige Wert, den du verlierst, ist der diagonale Wert. Bewahre ihn deshalb in einer Variable auf: Speichere den alten Wert von row[j], bevor du ihn überschreibst, und verwende ihn als Diagonalwert für j + 1.

Python

def minDistance(word1, word2):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

word1 = "spot"
word2 = "stop"

Erwartet

Edit Distance

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere alle drei Änderungen mit Rekursion aus

Fülle eine Tabelle mit Präfixen aus

Behalte nur zwei Zeilen

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben