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

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] minDis = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i <= word1.length(); i ++)
            minDis[i][0] = i;
        for(int j = 0; j <= word2.length(); j ++)
            minDis[0][j] = j;
        
        for(int i = 1; i <= word1.length(); i ++)
            for(int j = 1; j <= word2.length(); j ++) {
                int temp = Math.min(minDis[i-1][j], minDis[i][j-1]) + 1;
                if(word1.charAt(i-1) == word2.charAt(j-1))
                    minDis[i][j] = Math.min(temp, minDis[i-1][j-1]);
                else
                    minDis[i][j] = Math.min(temp, minDis[i-1][j-1]+1);
            }
        return minDis[word1.length()][word2.length()];
    }
}