edit distance

1def minDistacne(word1, word2):
2    # word1 -> laid horizontally
3    # word2 -> laid vertically
4
5    dp = [[0 for _ in range(len(word1) + 1)] for _ in range(len(word2) + 1)]
6
7    for row in range(len(word2) + 1):
8        for col in range(len(word1) + 1):
9            if row == 0:
10                dp[row][col] = col
11            elif col == 0:
12                dp[row][col] = row
13            elif word2[row - 1] == word1[col - 1]:
14                dp[row][col] = dp[row - 1][col - 1]
15            else:
16                dp[row][col] = 1 + min(
17                    dp[row - 1][col - 1], dp[row - 1][col], dp[row][col - 1]
18                )
19    return dp[len(word2)][len(word1)]
20
21
22if __name__ == "__main__":
23    a = minDistacne("horse", "ros")
24    print(a)
25