Description:

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1.Insert a character
2.Delete a character
3.Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Solution: 第一反应是动态规划

Solution DP v1: Your runtime (248 ms) beats 10.23 % of python3 submissions.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [list(range(len(word1)+1))]
        for row in range(1,len(word2)+1):
            dp.append([row]+[-1]*len(word1))
        
        for row in range(1,len(word2)+1):
            for col in range(1,len(word1)+1):
                dp[row][col] = min(dp[row][col-1]+1, 
                                   dp[row-1][col]+1, 
                                   dp[row-1][col-1]+1-int(word2[row-1] == word1[col-1]))
            
        return dp[-1][-1]

Solution DP v2: Your runtime (204 ms) beats 36.62 % of python3 submissions.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        last_line = list(range(len(word1)+1)) # from tracking a matrix dp(m,n) to 2 lines
        
        for row in range(1,len(word2)+1):
            current_line = [row] # another line
            for col in range(1,len(word1)+1):
                current_line.append(min(current_line[-1]+1, 
                                   last_line[col]+1, 
                                   last_line[col-1]+1-int(word2[row-1] == word1[col-1])))
            last_line = current_line
            
        return last_line[-1]

Solution DP v3: Runtime: 156 ms, faster than 84.43% of Python3 online submissions for Edit Distance.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        last_line = list(range(len(word1)+1))
        
        for row in range(1,len(word2)+1):
            current_line = [row]
            for col in range(1,len(word1)+1):
                if word2[row-1] == word1[col-1]:
                    current_line.append(last_line[col-1]) # change
                else:
                    current_line.append(1 + min(current_line[-1],last_line[col],last_line[col-1]))
                                   
            last_line = current_line
            
        return last_line[-1]

sample 64 ms submission: 还没研究透

from collections import deque

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        seen = set()
        q = deque([(word1, word2, 0)])
        
        while q:
            (w1, w2, d) = q.popleft()
            
            if w1 == w2:
                return d
            
            if (w1, w2) in seen:
                continue
            else:
                seen.add((w1, w2))
                
            while w1 and w2 and w1[0] == w2[0]:
                w1 = w1[1:]
                w2 = w2[1:]
                
            q.append((w1, w2[1:], d + 1))       # remove
            q.append((w1[1:], w2, d + 1))       # insert
            q.append((w1[1:], w2[1:], d + 1))   # replace

Train of thoughts: 下面这个链接有很好的讲解，所以我就不画图了

http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-72-edit-distance/