LEETCODE 72. Edit Distance 解题思路分析

题目大意：

编辑距离

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

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

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

示例 1:

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

示例 2:

输入: word1 = "intention", word2 = "execution" 
输出: 5 
解释:  intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=72

解题思路：

这道题题目很好理解，但是解题思路需要仔细来思考一下。最优解还是使用动态规划DP算法。

关于动态规划，我们已经分析过很多题目，关键要思考3步：

1. 如何定义一个dp数组。
2. 给出数组的起始条件。
3. 找出推导公式。直到利用公式算出dp数组的最后一个值，即为答案。

按照惯例，我们先定义一个二维数组dp[i][j]，表示word1的前i位变换成word2的前j位需要多少步。

接下来考虑起始条件，起始条件一般使用极端情况来考虑，比如当dp数组的i为0时，即word1的前0位变换成word2的前j位需要多少步？前0位代表空，一个空字符串想变成另一个字符串的步数，一定是另一个字符串的长度。所以dp[0][j] = j。同理，我们考虑下如果j为0呢？也就是说想将word1的前i位变换成一个空字符串需要多少步，这个步数也应该是word1前i位的长度，即dp[i][0] = i;

最后再考虑推导公式，利用推导公式和已知的起始条件我们可以逐步推导出最终答案，即word1的所有位转化为word2所有位所需要的步数。推导公式要分情况来考虑。如果word1的当前位等于word2的当前位，即当前位不需要做变换，所以当前位的步数dp[i][j]应等于其前一位的变换次数，即dp[i][j] == dp[i-1][j-1]。

如果word1和word2的当前位不一致时，我们应作出变换，变换有三种形式，分别是word1增加一个字符，减去一个字符，或替换掉当前字符，这三种操作分别可用dp[i][j-1]+1，dp[i-1][j]+1和dp[i-1][j-1]+1来表示，因为是求最优解，所以，当前位置dp[i][j]应该等于其中的最小值。

关于增删改这三种操作为何对应上面的公式，我看很多文章都没有讲清楚，这里再啰嗦两句。

我们举例来说明，比如：

word1 = "abc"
word2 = "acc"

如果当前i和j的坐标都是1，因为当前位b不等于c，我们决定尝试为word1增加一个字符c使得当前位的两字符相同，那么其实就是将word1的第0位a变成ac的过程，word1的第0位其实就是i-1，word2位置不变，即dp[i-1][j]，这个步数知道了，再做增操作将word1变为ac，最终的步数即dp[i-1][j]+1。同理，大家可以思考下另外两种操作。

看下完整代码：

public int minDistance(String word1, String word2) {
    int[][] dp = new int[word1.length() + 1][word2.length() + 1]; // 将word1的前n位转化为word2的前m位需要多少步
    for (int m = 0; m <= word1.length(); m++) {
        for (int n = 0; n <= word2.length(); n++) {
            if (m == 0) {
                dp[0][n] = n; // 初始条件
            } else if (n == 0) {
                dp[m][0] = m; // 初始条件
            } else if (word1.charAt(m - 1) == word2.charAt(n - 1)) {
                // 当前位相同时，不需要额外增加步数，即当前步数是上一位的步数
                dp[m][n] = dp[m - 1][n - 1];
            } else {
                // 当前位不同时，在增，删，改三种操作中找到最小步数再加上1
                dp[m][n] = Math.min(dp[m - 1][n - 1], Math.min(dp[m - 1][n], dp[m][n - 1])) + 1;
            }
        }
    }
    return dp[word1.length()][word2.length()];
}

本题解法6ms。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-72-edit-distance-解题思路分析/