leetcode刷题笔记-72.编辑距离问题

问题

https://leetcode.cn/problems/edit-distance/

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

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

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

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 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')

提示：

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

思路

这道题基于583.两个字符串的删除操作上，将只可以删除一个字符改成了可以进行删除、替换、插入操作。但本质还是两个字符串进行比较，所以大部份代码都是一模一样的，只有比较时两个字符不相同的时候的操作才有区别。

首先是定义dp数组，还是采用常用的定义方式

  • dp[i][j]：将字符串1的i之前和字符串2的j之前变成相同字符串的最少操作次数。

然后是确定dp数组的递推，首先是word1[i-1]和word2[j-1]相同和不相同这两种大情况

  • 当word1[i-1] == word2[j-1]，相当于不需要进行操作，dp[i][j]=dp[i-1][j-1];
  • 当word[i-1] != word2[j-1]，就需要进行编辑修改了；

当二者不同的时候，有多种方式进行修改，题目给出的是删除、替换、插入。但其实插入和删除是等价的！给出下面这两个字符串

1
word1="a" word2="ab"

假设我们进行删除，可以从word2中删除b字符，操作数是1；而进行插入是给word1插入一个字符b，操作数也是1。二者的操作数相同，那么递推公式也就相同，所以插入和删除可以认为是一种操作方式！

和583题不同的点就在于有一个替换的操作方式，当两个字符不同的时候，我们可以直接替换其中一个字符串中的字符，替换后两个字符就相等了，也就变成了word1[i-1] == word2[j-1]的情况，dp[i][j]==dp[i-1][j-1]+1;

最终的递推方案如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if (word1[i-1] == word2[j-1]) {
	// 二者相等，不需要做额外操作，沿用前一位的结果
	dp[i][j] = dp[i - 1][j - 1];
} else {
	// 二者不相等，分为三种操作情况，其中插入一个字符和删除一个字符等价
	// 1.在word1中删除一个字符
	int action1 = dp[i - 1][j] + 1;
	// 2.在word2中删除一个字符
	int action2 = dp[i][j - 1] + 1;
	// 3.二者都删除一个字符
	int action3 = dp[i - 1][j - 1] + 2;
	// 4.在word1或者word2中替换一个字符，那就是使用一次操作让二者相等；
	//   可以理解为是先把二者视作相等，然后加一次因为替换而产生的步骤；
	int action4 = dp[i - 1][j - 1] + 1;
	// 得到最小值
	dp[i][j] =
		min(min(action1, action2), min(action3, action4));
}

但实际上，这里完全可以省略583题目中两个字符串中都删除字符的操作，因为它的值很明显比替换字符需要的操作数多一次，进行min计算是没有意义的。

初始化和遍历方式都和583题目完全一样，可以去看站内之前写的583题目的题解，这里就不赘述了。

代码

完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int minDistance(string word1, string word2) {
        size_t sz1 = word1.size(), sz2 = word2.size();
        if (sz1 == 0 || sz2 == 0) {
            return sz1 == 0 ? sz2 : sz1;
        }
        // 1中i之前和2中j之前的字符串的最小编辑距离
        vector<vector<int>> dp(sz1 + 1, vector<int>(sz2 + 1, 0));
        // 初始化情况，dp[0][0]是两个空字符串，不需要编辑，初始化为0
        // i=0的情况和j=0的情况都是初始化为另外一个字符串的长度
        for (int i = 1; i <= sz1; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= sz2; j++) {
            dp[0][j] = j;
        }
        // 开始遍历
        for (int i = 1; i <= sz1; i++) {
            for (int j = 1; j <= sz2; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    // 二者相等，不需要做额外操作，沿用前一位的结果
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 二者不相等，分为三种操作情况，其中插入一个字符和删除一个字符等价
                    // 1.在word1中删除一个字符
                    int action1 = dp[i - 1][j] + 1;
                    // 2.在word2中删除一个字符
                    int action2 = dp[i][j - 1] + 1;
                    // 3.二者都删除一个字符，但这会比第四点耗费多一次操作，没意义
                    // int action3 = dp[i - 1][j - 1] + 2;
                    // 4.在word1或者word2中替换一个字符，那就是使用一次操作让二者相等
                    int action4 = dp[i - 1][j - 1] + 1;
                    // 得到最小值
                    dp[i][j] = min(min(action1, action2), action4);
                    // cout << i << " " << j << ":" << dp[i][j] << endl;
                }
            }
        }
        return dp[sz1][sz2];
    }
};

image.png