Editierdistanz Schritt für Schritt
Fügen Sie ein, löschen und ersetzen Sie, um eine Umwandlung vorzunehmen
Editierdistanz Schritt für Schritt ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was die Editierdistanz misst
Die Editierdistanz ist die kleinste Anzahl einzelner Zeichenänderungen, mit denen eine Zeichenkette in eine andere umgewandelt wird. Sie bewertet, wie unterschiedlich zwei Wörter tatsächlich sind.
Die drei Operationen
Sie dürfen pro Änderung ein Zeichen einfügen, löschen oder ersetzen. Bei der Standardaufgabe kostet jede Operation genau 1.
Zustand definieren
Sei dp[i][j] die Anzahl der Änderungen, mit denen die ersten i Zeichen von A in die ersten j Zeichen von B umgewandelt werden.
Kostenlose Übereinstimmung
Wenn die aktuellen Zeichen bereits übereinstimmen, ist keine Änderung erforderlich. Sie übernehmen einfach den diagonalen Wert unverändert.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Andernfalls zahlen Sie 1
Wenn sich die Zeichen unterscheiden, wählen Sie den günstigsten Nachbarn und addieren eine Änderung. Dieses min plus one deckt alle drei Operationen ab.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Welcher Nachbar steht wofür
Die Zelle darüber steht für ein Löschen, die Zelle links für ein Einfügen und die diagonale Zelle für ein Ersetzen. Das Minimum wählt einfach die günstigste Möglichkeit.
Basisfälle für leere Zeichenketten
Um eine Zeichenkette der Länge i in eine leere umzuwandeln, benötigen Sie i Löschungen. Füllen Sie daher die erste Zeile und Spalte mit 0, 1, 2 und so weiter.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jTabellengröße festlegen
Verwenden Sie ein Gitter der Größe n+1 mal m+1, damit die leeren Präfixe eine eigene Zeile und Spalte erhalten. Dieses Padding hält die Schleifen einfach.
dp = [[0] * (m+1) for _ in range(n+1)]In der richtigen Reihenfolge ausfüllen
Durchlaufen Sie i und j aufsteigend ab 1. Jede Zelle hängt nur von bereits ausgefüllten Nachbarn oben, links und diagonal ab.
for i in range(1, n+1):
for j in range(1, m+1):
...Distanz ablesen
Die minimale Anzahl an Änderungen landet in der Ecke. Ihre Antwort ist dp[n][m], sobald die Tabelle vollständig ist.
distance = dp[n][m]Kosten und Varianten
Das Verfahren benötigt O(n times m) Zeit. In realen Aufgaben können für die einzelnen Operationen unterschiedliche Kosten gelten, aber dieselbe Rekurrenz funktioniert weiterhin.
Schnelltest
Die Zeichen A[i-1] und B[j-1] unterscheiden sich. Welche Rekurrenz liefert die Editierdistanz?
Zusammenfassung: Editierdistanz
Bei einer Übereinstimmung übernehmen Sie den diagonalen Wert; bei einer Abweichung nehmen Sie 1 plus das Minimum der drei Nachbarn. Initialisieren Sie die Ränder und lesen Sie dp[n][m] ab. ✏️
Häufig gestellte Fragen
Ist die Lektion „Editierdistanz Schritt für Schritt“ kostenlos?
Ja — der vollständige Text von „Editierdistanz Schritt für Schritt“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Editierdistanz Schritt für Schritt“?
Fügen Sie ein, löschen und ersetzen Sie, um eine Umwandlung vorzunehmen Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Editierdistanz Schritt für Schritt“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Pfade in einem Raster zählen
- Minimale Pfadsumme mit Hindernissen
- Längste gemeinsame Teilfolge
- Editierdistanz Schritt für Schritt