七十二.编辑距离

  1.                                        ![image.png](https://cdn.nlark.com/yuque/0/2021/png/1068276/1615974558417-e6a591aa-8c5b-4e83-b6ca-1351da1523e6.png#align=left&display=inline&height=369&margin=%5Bobject%20Object%5D&name=image.png&originHeight=369&originWidth=456&size=17390&status=done&style=none&width=456)<br />题目中的三种操作本质上其实可以分为
  • 给 word1 插入一个字符：如果知道 word1 到 word2-1 的编辑次数 a，那么显然只需要 a+1 就能够得到结果
  • 给 word2 插入一个字符：如果知道 word1 到 word2-1 的编辑次数 b，那么显然只需要 b+1 就能够得到结果
  • 修改 word1 的一个字符：如果知道 word1 到 word2-1 的编辑次数 c，那么显然只需要 c+1 就能够得到结果

因此 word1 到 word2 的编辑距离应该是 min(a+1, b+1, c+1)

根据这个本质，我们可以继续拆分出更小的子编辑次数，直到 word1 和 word2 为空串，下面以 horse 和 ros 为例

  • word1 为空，我们就知道需要编辑 3 次，才能达到 word2 的长度
  • word2 为空，我们就知道需要编辑 5 次，才能达到 word1 的长度

因此，可以设 dp[i][j] 表示 word1[1…i] 位置转换成 word[1…j] 需要的最少编辑次数
当 word1[i]==word2[j] 时，dp[i-1][j-1]==dp[i][j]
否则 dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

  • dp[i][j-1] 为 word1 的前 i 个字符和 word2 的前 j - 1 个字符编辑距离的子问题。即对于 word2 的第 j 个字符，我们在 word1 的末尾添加了一个相同的字符，那么 dp[i][j] 最小可以为 dp[i][j-1] + 1
  • dp[i-1][j] 为 word1 的前 i - 1 个字符和 word2 的前 j 个字符编辑距离的子问题。即对于 word1 的第 i 个字符，我们在 word2 的末尾添加了一个相同的字符，那么 dp[i][j] 最小可以为 dp[i-1][j] + 1
  • dp[i-1][j-1] 为 word1 前 i - 1 个字符和 word2 的前 j - 1 个字符编辑距离的子问题。即对于 word2 的第 j 个字符，我们修改 word1 的第 i 个字符使它们相同，那么 dp[i][j] 最小可以为 dp[i-1][j-1] + 1。特别地，如果 word1 的第 i 个字符和 word2 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，dp[i][j] 最小可以为 dp[i-1][j-1]

因此不难写出代码

class Solution {
    public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();

        int[][] dp = new int[l1+1][l2+1];
        for (int i = 0; i <= l1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= l2; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i][j-1]),  dp[i-1][j])+1;
                }
            }
        }
        return dp[l1][l2];
    }
}