题解 | #编辑距离#

动态规划思路 :

1. 定义状态,f(i,j) 表示 word1 前 i 个字符(不包括 i) ,word2 前 j 个字符(不包括 j),转换最少的步骤!

2. 确定状态转移方程(即迭代方向) f(i,j) = if(word1[i-1] != word2[j-1]) min(f(i-1,j-1) + 1,f(i-1,j) + 1,f(i,j-1) + 1)

else min(f(i-1,j-1),f(i,j-1)+1,f(i-1,j) + 1); 可以发现,只要是发生了 插入 或者 删除,一定会增加 1步 操作;

f(i-1,j-1) 即代表替换的情况! f(i,j-1),f(i-1,j) 即代表删除 word1[i-1] 或添加 word2[j-1] !

3. 状体初始化,f(0,0) = 0;//替换 f(i,0) = i; // 插入 f(0,j) = j; //删除

可以看到,下一层的迭代依赖于上层和左边的部分,所以我们采用从上到下,从左到右的迭代!

话不多说 看代码:

    public int minDistance (String word1, String word2) {
        // write code here
        // 总共 三种情况 插入,修改
        // 插入和删除 需要注意!
        // 如果是 替换 , 结果 = 左上角  + word1[i-1] == word2[j-1] ? 0 : 1;
        // 如果是 插入 , 结果 = 左边 + 1; 一旦有插入或删除 操作定加 1;
      	// 如果是 删除 , 结果 = 上边 + 1; 一旦有插入或删除 操作定加 1;
      
        int m = word1.length();
        int n = word2.length();
        char[] arr1 = word1.toCharArray();
        char[] arr2 = word2.toCharArray();
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 0;
        for(int i = 1; i <= m; i++){
            dp[i][0] = i;
        }
        for(int i = 1; i <= n; i++){
            dp[0][i] = 1;
        }
       
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
              	// 无论任何情况下,当选择插入或删除 都需要相同的推导
              	// 这里做个简化!
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + 1;
                if(arr1[i-1] != arr2[j-1]){
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1] + 1);
                }else {
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1]);
                }
            }
        }
        return dp[m][n];
    }