Freiwillige Abgabe als .py-Datei (bei mehreren Dateien als .zip komprimiert) an e.nie@campus.lmu.de bis 23.12.2021.
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:
m = len(word1)
n = len(word2)
# if one of the two words is empty string
if m * n == 0:
return m + n
# Step 1: create an empty DP array of m * n
DP = [ [0] * (n + 1) for _ in range(m + 1)]
# Step 2: initialize the edge states
for i in range(m + 1):
DP[i][0] = i
for j in range(n + 1):
DP[0][j] = j
# Step 3: Calculate all state values using state transition equation
for i in range(1, m + 1):
for j in range(1, n + 1):
f = 0 if word1[i-1] == word2[j-1] else 1
# state transition equation
DP[i][j] = min(DP[i-1][j] + 1,
DP[i][j-1] + 1,
DP[i-1][j-1] + f)
# get the result
return DP[m][n]
# test
word1, word2 = "horse", "rose"
print(edit_distance(word1, word2))
2