Find the Edit Distance Between Two Words (Deprecated)
Given two words, find the minimum number of edits to mutate one word into the other. Tags: Dynamic Programming, Recursion
Try It!
Discussion
Video
Solution
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0 for x in range(len(word2) + 1)] for y in range(len(word1) + 1)]
for y in range(len(word1) + 1):
dp[y][0] = y
for x in range(len(word2) + 1):
dp[0][x] = x
for y in range(1, len(word1) + 1):
for x in range(1, len(word2) + 1):
if word1[y - 1] == word2[x - 1]:
dp[y][x] = dp[y - 1][x - 1]
else:
dp[y][x] = 1 + min([
dp[y - 1][x],
dp[y][x - 1],
dp[y - 1][x - 1],
])
return dp[len(word1)][len(word2)]