[leetcode] edit Distance

算法思想 动态规划。

假设字符下标从1开始。

c[i][j] 表示word1[1~i] 到word2[1~j]的最短编辑距离。

则有递推式：

c[i][j] = min(c[i-1][j],c[i][j-1],c[i-1][j-1])+1; if(i >= 1 && j >= 1 && word[i] != word[j])

           c[i-1][j-1];     if(i >= 1 && j >= 1 && word[i] == word[j])         

 当i == 0|| j ==0时，忽略计算上述中的对应项即可。

说明： c[i][j] = c[i-1][j]+1 表示执行的是删除操作；

            c[i][j] = c[i][j-1]+1表示执行的是插入操作；

            c[i][j] = c[i-1][j-1] 在word[i]!=word[j] 时表示执行的是替换操作；

 

代码：

public class Solution {
    /*
    c[m+1][n+1]数组 认为word1,word2的下标都是从1开始。因此取具体字符的时候应该注意是i-1,j-1
    初始化c[0][0] = 0 
    */
    public int minDistance(String word1, String word2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(word1 == null||word1.length() == 0) return word2.length();
        if(word2 == null||word2.length() == 0) return word1.length();
        int m = word1.length();
        int n = word2.length();
        
        int c[][] = new int[m+1][n+1];
        
        c[0][0] = 0;
        
        for(int j = 1;j<=n;j++)
            c[0][j]  = j;
        for(int i = 1;i<=m;i++)
            c[i][0] = i;
        for(int i = 1;i<=m;i++)
            for(int j = 1; j<=n;j++){
                int min = c[i-1][j-1];
                if(min>c[i][j-1]) min = c[i][j-1];
                if(min>c[i-1][j]) min = c[i-1][j];
                c[i][j] = min+1;
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                   if(c[i][j] > c[i-1][j-1]) c[i][j] = c[i-1][j-1];
                }
            }
        return c[m][n];
    }
}