「这是我参与11月更文挑战的第4天，活动详情查看：2021最后一次更文挑战」

前言

力扣第七十二题 编辑距离 如下所示：

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 **所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入： word1 = "horse", word2 = "ros"
输出： 3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
复制代码

一、思路

这一题我刚开始看到的时候也是不知道从何处下手，后面也是看了题解才知道可以从 动态规划 下手。

这一题最重要的就是要知道 dp[i][j] 是 words1 的前 i 个字符到 word2 的前 j 个字符的编辑距离。

我们可以得到如下的状态转移方程：

• 若 A 和 B 的最后一个字母相同：D[i][j] = min(D[i][j-1]+1, D[i-1][j]+1, D[i-1][j-1])
• 若 A 和 B 的最后一个字母不同：D[i][j] = 1 + min(D[i][j-1], D[i-1][j], D[i-1][j-1])

后面就是 动态规划 中的填写二维数组的内容了，大致的步骤如下所示：

1. 初始化边界内容，dp[i][0] = i 和 dp[0][j] = j（dp[i][0] = i 相当于需要删除了 i 次，dp[0][j] = j 相当于插入 j 次）
2. 双层循环遍历，填满 dp[i][j]
3. 返回 dp[word1.length][words2.length] 的值即可

图解算法

此处以 word1 = "horse", word2 = "ros" 作为例子

1. 初始化边界值后，dp[][] 如下所示

2. 根据状态转移方程填充第一行

先判断 words1[i] 与 words2[j] 是否相等

• 如果相等：取 左边的值 + 1、上边的值 + 1、左上角的值 中的最小值作为结果
• 如果不相等：取 左边的值 + 1、上边的值 + 1、左上角的值 + 1 中的最小值作为结果

3. 填充第二行

4. 填充后续的行

5. 返回右小角 dp[i][j] 的结果 3 即可

二、实现

实现代码

注意：为了将 i j 的坐标与数组对齐，在初始化二维数组时，二维数组为dp[len1 + 1][len2 + ]

    /**
     * 动态规划
     */
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        // 下标对齐
        int[][] dp = new int[len1+1][len2+1];
        // 初始化边界值
        for (int i=1; i<len1+1; i++) {
            dp[i][0] = i;
        }
        for (int j=1; j<len2+1; j++) {
            dp[0][j] = j;
        }
        // 遍历
        for (int i=1; i<len1+1; i++) {
            for (int j=1; j<len2+1; j++) {
                // 判断是否相等
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1]);
                } else {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
复制代码

测试代码

    public static void main(String[] args) {
        new Number72().minDistance("horse", "ros");
    }
复制代码

结果

三、总结

感谢看到最后，非常荣幸能够帮助到你~♥

如果你觉得我写的还不错的话，不妨给我点个赞吧！如有疑问，也可评论区见~