1. question: 编辑距离(困难)
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/edit-distance
示例 1:
1 | 输入:word1 = "horse", word2 = "ros" |
示例 2:
1 | 输入:word1 = "intention", word2 = "execution" |
提示:
1 | 0 <= word1.length, word2.length <= 500 |
2. answers
这道题比较难。最开始做的时候,没有做过类似的题目。上一道删除操作的题目,按照公共子序列做的,后续添加了删除思路。
动态规划这种题目不变的思路就是找递推公式。
定义数组dp[i][j]表示,word1[0:i]和word2[0:j]相同所需的最低次操作。那么word1[0:i+1]和word2[0:j+1]相同,所需的最低次操作该怎么计算呢?显然有如下几种情况:
- 二者字符相同,即word1[i+1]和word2[j+1]相同,dp[i+1][j+1] = dp[i][j]。
- 二者不等,此时可有三种选择:
- 删除字符
- 删除word1[i+1],dp[i+1][j+1] = dp[i][j+1] + 1
- 删除word2[j+1],dp[i+1][j+1] = dp[i+1][j] + 1
- 二者都删除,dp[i+1][j+1] = dp[i][j] + 2
- 替换字符(修改字符):当前两个字符参与比较。无论替换哪个,都是最后两个元素相等。
- 替换word1[i+1],dp[i+1][j+1] = dp[i][j] + 1
- 替换word2[i+1],dp[i+1][j+1] = dp[i][j] + 1
- 插入字符(新增字符):即插入和另一个字符串结尾相同的字符
- 在word1结尾插入word2[j+1]字符,此时就是word1[i+1]和word2[j]字符串相同,dp[i+1][j+1] = dp[i+1][j] + 1
- 在word2结尾插入word1[i+1]字符,此时就是word1[i]和word2[j+1]字符串相同,dp[i+1][j+1] = dp[i][j+1] + 1
- 注意,是在结尾插入,不是在当前字符的前面插入,而是结尾!因此比较的是dp[i][j-1]和dp[i-1][j]
- 上面的7中选择,选最小值即可。显然第3种,一定小于45种,12种和67种相同。因此最终只有三类选择。
一定要理解插入和替换的操作,究竟是谁和谁匹配。
代码如下所示:
1 | public class Solution_0144 { |
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。