Edit distance

Question

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example Given word1 = "mart" and word2 = "karma", return 3.

Thoughts

与前面类似，主要是思考 当相等时，可以进行什么操作 当不等时，可以进行什么操作

Solution

class Solution: 
    # @param word1 & word2: Two string.
    # @return: The minimum number of steps.
    def minDistance(self, word1, word2):
        # write your code here
        if not word1:
            return len(word2)
        if not word2:       
            return len(word1)  
        dp = [[0 for j in range(len(word2)+1)] for i in range(len(word1)+1)]
        for j in range(len(word2)+1):
            dp[0][j] = j
        for i in range(len(word1)+1):
            dp[i][0] = i

        for i in range(1, len(word1)+1):  
            for j in range(1, len(word2)+1):                         
                    if word1[i-1] == word2[j-1]:                        
                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]+1, dp[i][j-1]+1)   
                    else:        
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 
        return dp[len(word1)][len(word2)]