LeetCode72 编辑距离 解题思路和AC代码

一.题目

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二.解体思路

这一道题读完之后感觉很复杂，完全不知道怎么入手。如果从动态规划的角度考虑。我们看到这个题目中有两个字符串，想到是不是可以用一个二维数组作为dp。dp的长和宽就是两个字符串的长度。那么dp[i][j]表达什么含义呢？因为要求的是word1转换为word2的步骤。那么它的子问题可以为word1的前i个字符转换为word2的前j个字符。这也就是dp[i][j]的含义。

定义出问题来，之后就是找递推公式和初始化了。

先考虑递推公式。一般来说dp[i][j]经常由dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]来推导出来。对于这道题适不适用呢？答案是肯定的。可以按word1[i]是否和word2[j]相等来分为两种情况讨论。

总结：这一题属于用二维数组作为dp数组的题目。关键是dp[i][j]可以用d[i-1][j-1]等可以推导出来。题目为变量1的前i个字符转换为变量2的前j个字符。与这一题类似的还有

三.AC代码

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(),m = word2.length();
        int[][] dp = new int[n + 1][m + 1];
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for(int j = 1; j <= m; j++) {
            dp[0][j] = j;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1] - 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[n][m];
    }
}