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)]