Übung Basismodul Computerlinguistik

Hausaufgabe 07

16.12.21

Freiwillige Abgabe als .py-Datei (bei mehreren Dateien als .zip komprimiert) an e.nie@campus.lmu.de bis 23.12.2021.

1. Aufgabe Edit-Distanz

Gegeben seien zwei Strings word1 und word2, schreibe eine Funktion, die word1 und word2 annimmt, und die Edit-Distanz (die minimal benötigte Anzahl von Operationen, um word1 to word2 zu konvertieren) zurückgibt.

Hint: Verwende den Algorithmus Dynamische Programmierung.

Example: Input: word1 = "horse", word2 = "rose" Output: 2

def edit_distance(word1: str, word2: str) -> int:
    pass

# test
word1, word2 = "horse", "rose"
print(edit_distance(word1, word2))