72. Edit Distance

# Hard （非常经典，一定要会）

典型的二维序列DP问题，即需要一个二维数组来记录关键信息，这道题经常考

Solution:

1. Initilize minDis[i][j], 这种一定是初始化横行和纵行。minDis[i][j] means the minimum distance of converting from word1[:i+1] to word2[:j+1]. One extra empty element in minDis is very necessary, because following elements are based on the previous elemens.

2. Three cases may affect minDis.

   1. minDis[i-1][j] + 1 次转换

   2. minDis[i][j-1] + 1 次转换

   3. word1[i-1] = word2[j-1], 所以不用转换, minDis[i-1][j-1]

   从中找一个最小值赋值给minDis[i][j]即可。

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # two-sequence DP problem
        # initialize minDis, minDis[i][j] means min distance from word1[:i+1] to word2[:j+1]
        minDis = [[float('Inf')]*(len(word2)+1) for i in range(len(word1)+1)]

        for i in range(len(word1)+1):
            minDis[i][0] = i
        for j in range(len(word2)+1):
            minDis[0][j] = j
            
        # compute
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                minDis[i][j] = min(minDis[i-1][j], minDis[i][j-1]) + 1
                if word1[i-1] == word2[j-1]:
                    minDis[i][j] = min(minDis[i][j], minDis[i-1][j-1])
                else:
                    minDis[i][j] = min(minDis[i][j], minDis[i-1][j-1]+1)
        
        return minDis[len(word1)][len(word2)]p

Java(O(mn))