BM75 编辑距离(一)

题意

编辑距离(一)_牛客题霸_牛客网 (nowcoder.com)

思路

主要难点是如何建立dp数组，我当时想的是（i，j）表示的是i和j的区间已经完成操作，但是递推方程需要左边和右边都有，所以不行后续的j表示长度的话也不行。忘得太快了。。。。

题解 | #编辑距离(一)#_牛客博客 (nowcoder.net)

把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转移，那可以考虑动态规划。用dp[i][j]表示从两个字符串首部各自到str1[i]和str2[j]为止的子串需要的编辑距离，那很明显dp[str1.length][str2.length]就是我们要求的编辑距离。（下标从1开始）

具体做法：

• step 1：初始条件： 假设第二个字符串为空，那很明显第一个字符串子串每增加一个字符，编辑距离就加1，这步操作是删除；同理，假设第一个字符串为空，那第二个字符串每增加一个字符，编辑距离就加1，这步操作是添加。
• step 2：状态转移： 状态转移肯定是将dp矩阵填满，那就遍历第一个字符串的每个长度，对应第二个字符串的每个长度。如果遍历到str1[i]和 str2[j]的位置，这两个字符相同，这多出来的字符就不用操作，操作次数与两个子串的前一个相同，因此有dp[i][j]=dp[i-1][j-1]；如果这两个字符不相同，那么这两个字符需要编辑，但是此时的最短的距离不一定是修改这最后一位，也有可能是删除某个字符或者增加某个字符，因此我们选取这三种情况的最小值增加一个编辑距离，即dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i][j])+1。

public int editDistance(String str1, String str2) {
       // write code here
       int len1 = str1.length();
       int len2 = str2.length();
       int[][] dp = new int[len1 + 5][len2 + 5];
       for (int i = 0; i <= len1; i++) {
           dp[i][0] = i;
       }
       for (int i = 0; i <= len2; i++) {
           dp[0][i] = i;
       }
       for (int i = 1; i <= len1; i++) {
           for (int j = 1; j <= len2; j++) {
               if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                   dp[i][j] = dp[i - 1][j - 1];
               } else {
                   dp[i][j] = dp[i - 1][j - 1] + 1;
                   dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j]);
                   dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i][j]);
               }
           }
       }
       return dp[len1][len2];
   }

算法全部代码参考leonyan18/AlgorithmCodeInJava (github.com)