● 583. 两个字符串的删除操作
注意审题:
给定两个单词 word1
和 word2
,返回使得 word1
和 word2
相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
删除最少的字符使两者相同,说明留下来的就是最大公共子序列。不要求连续,所以可以使用● 1143.最长公共子序列 来做,最长公共子序列之外的字母都要删除,所以返回 (n1+n2-2*dp[n1][n2]) 即可。
这是间接求法,直接求:
1.dp数组含义。
dp[i][j]:以word1[i-1]为结尾的字符串,和以word2[j-1]位结尾的字符串,想要达到相等,所需要删除元素的最少次数为dp[i][j]。
2.递推公式。
如果相等:删除次数要最少,那么相等的话就不能删除,得留着,所以dp[i][j]=dp[i-1][j-1];
如果不等:2个字符串没有谁长谁短的前提,所以应该有3种情况。
①可能删掉word1[i-1],那么dp[i][j]代表的子序列和dp[i-1][j]代表的子序列删除的字母,就多了一个:word1[i-1],所以dp[i][j]=dp[i-1][j]+1;
②可能删掉word2[j-1],同样,dp[i][j]=dp[i][j-1]+1;
③都删除。都删除的话,dp[i][j]代表的子序列和dp[i-1][j-1]代表的子序列删除的字母,就多了2个:word1[i-1]和word2[j-1],所以是dp[i][j]=dp[i-1][j-1]+2;这其实也是满足情况①和情况②的,删掉2个,和dp[i-1][j]相比多删了一个word2[j-1],和dp[i][j-1]相比多删了一个word1[i-1]。所以情况①/情况②就把③包含了。所以只取①和②的最小删除数量,即Min值就是对的。
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
3.初始化。
dp[i][0]。i>0时,word1[i-1]:非空串;word2[0,-1]:空串。所以应该删除word1的前i个达到相等。
dp[0][j]。同样应该删除word2的前j个达到相等。
dp[0][0]。不用删除,=0。
4.遍历顺序。
5.打印。
代码如下:
class Solution {
public:
int minDistance(string word1, string word2) {
int n1=word1.size();
int n2=word2.size();
vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
for(int i=1;i<=n1;++i)dp[i][0]=i;
for(int j=1;j<=n2;++j)dp[0][j]=j;
for(int i=1;i<=n1;++i){
for(int j=1;j<=n2;++j){
if(word1[i-1]==word2[j-1]){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//省略dp[i-1][j-1]+2;
}
}
}
return dp[n1][n2];
}
};
● 72. 编辑距离
1.dp数组含义。
dp[i][j]:数组1[0,i-1]中操作(插删换)dp[i][j]次,得到的序列是数组2[0,j-1]。注意这个操作过程是可逆的,2[0,j-1]中操作(删插换)dp[i][j]次,得到的序列是1[0,i-1]。
所以每一步操作,既可以对数组1操作,也可以对数组2操作。我觉得变换一下题目解法也没有变:请返回操作后使word1和word2相同的最大操作数。
举例:“horse”变成“ros”:
horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
因为,对数组1 的 插入 等同于对数组2 的删除,删除同理,那么:
ros -> rose (插入 'e');horse-> rorse(将 'h' 替换为 'r');rose -> rorse(插入 'r')。
即中间每步可以选择对1操作,也可以对2操作。可见操作后可以得到很多种相同字符串(horse、rorse、rose或ros),但是过程中数组1和数组2操作的次数之和是固定的,即编辑距离是固定的。
2.递推公式。
(1)不相等的话,这3个操作都有可能发生,那么是肯定要加上1(做一个操作)。
①替换:
可以1[i-1]替换成2[j-1],也可以2[j-1]替换成1[i-1]。改了之后,得到的2个子数组最后元素相同,所以应该是在dp[i-1][j-1]的基础上替换了1或2的一个元素,所以+1。
即dp[i][j]=dp[i-1][j-1]+1。
②可以删除:
删除1[i-1]达到相同,说明[0,i-2]中操作之后,就能得到2[0,j-1]了,所以是在这个基础(dp[i-1][j])之上加一个删除操作即可,即dp[i][j]=dp[i-1][j]+1。
也可以删除2[j-1]达到相同,那么同理,dp[i][j]=dp[i][j-1]+1。
③可以插入:
插入1[i-1]达到相同,代表着删除2[i-1]达到相同,上面说了只是操作不同但次数相同,所以在1或2插入的情况都可以用删除表示,所以1[i-1]后面插入的情况下dp[i][j]==dp[i][j-1]+1。2[j-1]后面插入的情况下dp[i][j]=dp[i-1][j]+1。上面都包含了。
所以:dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
(2)相等:和上题同样是求最少操作数,所以相等的话不操作,即dp[i][j]=dp[i-1][j-1]。
3.初始化。
回忆dp的含义:
dp[i][0]=i。以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0]。
dp[0][j]=j。同理。
4.遍历顺序。
从上到下,从左到右。
5.打印。
代码如下:
class Solution {
public:
int minDistance(string word1, string word2) {
int n1=word1.size();
int n2=word2.size();
vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
for(int j=0;j<=n2;++j)dp[0][j]=j;//删除
for(int i=0;i<=n1;++i)dp[i][0]=i;//插入
for(int i=1;i<=n1;++i){
for(int j=1;j<=n2;++j){
if(word1[i-1]==word2[j-1]){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;//,
}
}
}
return dp[n1][n2];
}
};
● 编辑距离总结篇
做多了总结一下:都是在dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]的基础上得到dp[i][j],要得到这个递推公式,就是得清楚,什么情况下,对A[i-1](B[j-1])做什么操作,比如上面● 72. 编辑距离,不相同的话,可能对A[i-1]和B[j-1]这一对,修改其中一个就行,所以是在dp[i-1][j-1]基础上+1……
总结一下3个编辑距离前导题: