edit distance algorihtm, code example
Example: edit distance
def minDistacne(word1, word2):
dp = [[0 for _ in range(len(word1) + 1)] for _ in range(len(word2) + 1)]
for row in range(len(word2) + 1):
for col in range(len(word1) + 1):
if row == 0:
dp[row][col] = col
elif col == 0:
dp[row][col] = row
elif word2[row - 1] == word1[col - 1]:
dp[row][col] = dp[row - 1][col - 1]
else:
dp[row][col] = 1 + min(
dp[row - 1][col - 1], dp[row - 1][col], dp[row][col - 1]
)
return dp[len(word2)][len(word1)]
if __name__ == "__main__":
a = minDistacne("horse", "ros")
print(a)