最小编辑距离

 

 

这道题也是leetcode72，

注意代码中的i，j代表第几个字符，0表示空串，所以比较word1的第i个与word2的第j个是 

if(word1[i-1] == word2[j-1])

    int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        for(int i = 0;i <= m;i++)  d[i][0] = i;
        for(int i = 0;i <= n;i++)  d[0][i] = i;
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= n;j++)
            {
                if(word1[i-1] == word2[j-1]) d[i][j] = d[i-1][j-1];
                else{
                    d[i][j] = min(d[i-1][j-1], min(d[i-1][j], d[i][j-1])) + 1;
                }
            }
        
        return d[m][n];
    }

还可以用滚动数组，去掉第一维节省空间（不会减少时间）

参考链接：《算法设计与分析》-董老师的PPT