LeetCode 72. 编辑距离 【c++java详细题解】

LeetCode 72. 编辑距离 【c++java详细题解】,第1张

LeetCode 72. 编辑距离 【c++/java详细题解】

目录

1、题目2、思路3、初始化4、c++代码5、Java代码

1、题目

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少 *** 作数 。

你可以对一个单词进行如下三种 *** 作:

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

示例 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')

提示:

0 <= word1.length, word2.length <= 500word1 和 word2 由小写英文字母组成 2、思路

(动态规划) O ( n ∗ m ) O(n * m) O(n∗m)

给你两个单词 word1 和 word2,我们可以对一个单词进行插入一个字符,删除一个字符,替换一个字符三种 *** 作,请你计算出将 word1 转换成 word2 所使用的最少 *** 作数 。

样例:

如样例所示,word1 = "horse", word2 = "ros",我们将word1转换成word2所使用的最少 *** 作数为3,下面来讲解动态规划的做法。

对于动态规划的题目来说,我们一般要考虑两个问题,分别是状态表示和状态计算。状态表示往往和题目的问题相关,因此我们可以定义如下状态表示。

状态表示: f[i][j] 表示将 word1 的前 i 个字符变成 word2 的前 j 个字符所需要进行的最少 *** 作次数。假设word1长度为n,word2长度为m,那么f[n][m]就表示将 word1 的前 n 个字符变成 word2 的前 m 个字符所需要进行的最少 *** 作次数,即为答案。

有了状态表示以后,我们去进行状态计算,推导状态计算方程。

状态计算:

如何计算f[i][j]?考虑word1的第i个字符与word2的第j个字符,分为两种情况:

1、word1[i] == word2[j],则f[i][j] == f[i - 1][j - 1];2、word1[i] != word2[j],我们有三种选择,替换、删除、插入:

替换: 替换word1的第i个字符或者替换word2的第j个字符,则f[i][j] == f[i - 1][j - 1] + 1;删除: 删除word1的第i个字符或者删除word2的第j个字符,则f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;插入: 在 word2[j] 后面添加 word1[i]或者在word1[i]后添加word2[j],则f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;

我们去解释一下上述状态计算:

当word1[i] == word2[j]时,当前两个字符相同,我们不需要做任何 *** 作,此时f[i][j]就可以从f[i - 1][j - 1]的状态转移过来,换句话说,此时f[i][j]的状态取决于f[i - 1][j - 1]。

当word1[i] != word2[j]时,此时我们可以进行的 *** 作有三种:

替换: 替换word1的第i个字符或者替换word2的第j个字符,当前位置的字符不匹配,进行替换 *** 作后两者变得相同。

所以f[i][j] == f[i - 1][j - 1] + 1。

删除: 删除word1的第i个字符或者删除word2的第j个字符。

如果当前word1[0 ~ i-1] 与word2[0 ~ j]匹配,我们删除多余的word1[i],或者word1[0 ~ i]与word2[0 ~ j-1]匹配,我们删除多余的word[j]。

两种情况的状态分别为f[i - 1][j]和f[i][j - 1],因为题目要求最少 *** 作数,故二者之间我们取一个最小值,所以f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1。

插入: 在 word2[j] 后面添加 word1[i]或者在word1[i]后添加word2[j]。

如果当前word1[0 ~ i-1] 与word2[0 ~ j]匹配或者word1[0 ~ i]与word2[0 ~ j-1]匹配,除了考虑删除多余的字符 *** 作以外,我们还可以执行添加 *** 作,因此添加和删除的状态计算其实是一样的。

所以f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1。

考虑完状态计算和状态转移以后,接下来我们去进行状态初始化。

3、初始化
for(int i = 0; i <= n; i++)  f[i][0] = i;  //将长度为i的word1变成长度为0的word2需要进行最少i次删除操作
for(int i = 0; i <= m; i++)  f[0][i] = i;  //将长度为i的word2变成长度为0的word1需要进行最少i次删除操作

实现细节:

其实我们可以注意到,word[]数组下标如果从1开始的话,第i个字符就是word[i],而不是下标从0开始的word[i - 1],这样的word[]数组与我们的状态表示会更加相对应。因此,为了代码的可读性更高,我们给word1[]数组和word2[]数组的开头都去添加一个空格,然后在状态计算时,下标从1开始。

时间复杂度分析: 状态数为 O ( n ∗ m ) O(n * m) O(n∗m),状态计算为 O ( 1 ) O(1) O(1),因此总的时间复杂度为 O ( n ∗ m ) O(n * m) O(n∗m)。

4、c++代码
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        word1 = ' ' + word1;  //添加空格
        word2 = ' ' + word2;
        vector>f(n + 1, vector(m + 1));
        for(int i = 0; i <= n; i++)  f[i][0] = i;  //i次删除
        for(int i = 0; i <= m; i++)  f[0][i] = i;  //i次删除 word1 -> word2
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;      //添加或者删除
                if(word1[i] == word2[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
                else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); //替换
            }
        return f[n][m];    
    }
};
5、Java代码
class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        word1 = ' ' + word1; //添加空格
        word2 = ' ' + word2;
        int[][] f = new int[n + 10][m + 10];
        for(int i = 0;i <= n;i++) f[i][0] = i; //i次删除
        for(int i = 0;i <= m;i++) f[0][i] = i; //i次删除 word1 -> word2
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
            {  
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1); //添加或者删除
                if(word1.charAt(i) == word2.charAt(j)) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);//替换
            }
        return f[n][m];
    }
}

原题链接: 72. 编辑距离

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5718399.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表(0条)

保存