Edit Distance
Die Edit Distance (auch als Levenshtein-Distanz bekannt) zwischen zwei Zeichenketten ist die minimale Anzahl an Operationen, um eine Zeichenkette in die andere zu transformieren. Erlaubte Operationen sind dabei:
- Einen einzelnen Buchstaben zur Zeichenkette hinzufügen.
- Einen einzelnen Buchstaben aus der Zeichenkette entfernen.
- Einen einzelnen Buchstaben in der Zeichenkette ersetzen.
Beispielsweise beträgt die Edit Distance zwischen und den Wert 2, da man zuerst durch ersetzen und anschließend ein hinzufügen kann.
Du erhältst zwei Zeichenketten und sollst die Edit Distance zwischen diesen beiden berechnen.
Eingabe
Die erste Zeile der Eingabe enthält die erste Zeichenkette, die zweite Zeile enthält die zweite Zeichenkette. Es wird garantiert, dass die Anzahl der Zeichen in beiden Zeichenketten 1000 nicht übersteigt.
Ausgabe
Das Programm soll eine einzelne Zahl ausgeben – die Edit Distance der beiden eingegebenen Zeichenketten.
Beispiele
Eingabe | Ausgabe |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB