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]
,就需要进行编辑修改了;
当二者不同的时候,有多种方式进行修改,题目给出的是删除、替换、插入。但其实插入和删除是等价的!给出下面这两个字符串
假设我们进行删除,可以从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 { int action1 = dp[i - 1][j] + 1; int action2 = dp[i][j - 1] + 1; int action3 = dp[i - 1][j - 1] + 2; 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; } vector<vector<int>> dp(sz1 + 1, vector<int>(sz2 + 1, 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 { int action1 = dp[i - 1][j] + 1; int action2 = dp[i][j - 1] + 1; int action4 = dp[i - 1][j - 1] + 1; dp[i][j] = min(min(action1, action2), action4); } } } return dp[sz1][sz2]; } };
|
![image.png](/img/loading.gif)