【LeetCode】72. 编辑距离
72. 编辑距离(困难)
-
思路
- 状态定义:「
dp[i][j]
表示第一个字符串到 i ,第二个字符串到 j,要想使得 word1 == word2 ,最少的修改次数」。 - 状态转移方程:
- 当第 i 位和第 j 位对应的字符相同时,
dp[i][j] = dp[i-1][j-1]
; - 当第 i 位和第 j 位对应的字符不同时,有三种修改方式:(1)替换第 i 位:
dp[i][j] = dp[i-1][j-1] + 1
;(2)删除第 i 位:dp[i][j] = dp[i-1][j] + 1
;(3)插入第 i 位:dp[i][j] = dp[i][j-1] + 1
。要使得修改次数最小,就是在三种方案中选择最小的 dp[i][j] ,即dp[i][j] = min(min(dp[i-1][j-1],dp[i-1][j]), dp[i][j-1]) + 1;
- 当第 i 位和第 j 位对应的字符相同时,
- 初始化: 需要考虑到 i=0 和 j=0 的情况,当i=0 时,那么只能选择插入,才能等于字符串 word2, 此时的操作次数为 word2 的长度(j),所以
dp[i][j] = j
;当 j=0 时,只能选择删除,此时的操作次数为 word1 的长度(即 i),所以dp[i][j] = i
;
- 状态定义:「
-
代码
class Solution { public:int minDistance(string word1, string word2) {int n1 = word1.size(), n2 = word2.size();vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));for(int i=0; i<=n1; ++i){for(int j=0; j<=n2; ++j){// 这题第一行和第一列需要额外初始化if(i == 0){// 第一个字符串为空,想要转变成第二个字符串// 需要有j(第二个字符串当前的长度)个插入操作dp[i][j] = j;}else if(j == 0){dp[i][j] = i;}else{if(word1[i-1] == word2[j-1]){// 两字符相同,无需修改dp[i][j] = dp[i-1][j-1];}else{// 指向的字符不相同,选择操作次数最小的修改方案dp[i][j] = min(min(dp[i-1][j-1],dp[i-1][j]), dp[i][j-1]) + 1;}}}}return dp[n1][n2];} };
-
收获
- 看到困难题就放弃了,不过思路蛮简单的,状态定义和 1143 (求两个字符串的最长公共子串)类似。因此对于比较两个字符串的题目,可以总结为: 「如果是比较两个字符串,那么状态就定义为 :
dp[i][j] 表示为 第一个字符串到 i ,第二个字符串到 j 为止的属性
」。 - 此外,不是所有 dp数组的初始化都为 0 ,像求得最小值的时候(如 322) ,就得定义一个较大的值,才便于比较;而像这题,需要具体考虑初始值。
- 看到困难题就放弃了,不过思路蛮简单的,状态定义和 1143 (求两个字符串的最长公共子串)类似。因此对于比较两个字符串的题目,可以总结为: 「如果是比较两个字符串,那么状态就定义为 :