兰州网站建设与优化推广,网站开发基础知识,手机版网站快照如何做,自动点击器怎么用● 583. 两个字符串的删除操作
注意审题#xff1a;
给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
删除最少的字符使两者相同#xff0c;说明留下来的就是最大公共子序列。不要求…● 583. 两个字符串的删除操作
注意审题
给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
删除最少的字符使两者相同说明留下来的就是最大公共子序列。不要求连续所以可以使用● 1143.最长公共子序列 来做最长公共子序列之外的字母都要删除所以返回 (n1n2-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]。i0时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 n1word1.size();int n2word2.size();vectorvectorint dp(n11,vectorint(n21,0));for(int i1;in1;i)dp[i][0]i;for(int j1;jn2;j)dp[0][j]j;for(int i1;in1;i){for(int j1;jn2;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 n1word1.size();int n2word2.size();vectorvectorint dp(n11,vectorint(n21,0));for(int j0;jn2;j)dp[0][j]j;//删除for(int i0;in1;i)dp[i][0]i;//插入for(int i1;in1;i){for(int j1;jn2;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个编辑距离前导题
判断子序列
判断s是不是t的子序列。根据最长公共子序列来做dp[i][j]不要求si-1、t[j-1]结尾。
2个元素相等的时候。dp[i][j]dp[i-1][j-1]1;
不相等。因为序列1一定比序列2短不相等的话dp[i][j-1]一定大于dp[i-1][j]所以dp[i][j]dp[i][j-1]
不同的子序列
统计序列s在序列t中出现的个数。
2个元素相同。s[i-1]有可能匹配t[j-1]以及t[j-1]之前的与之相等的元素。
所以dp[i][j]dp[i-1][j-1]dp[i-1][j-1]
不相同。s[i-1]只可能匹配t[j-1]之前的所以dp[i][j]dp[i-1][j]。
两个字符串的删除操作
统计序列s和序列t删除最少几个元素变成一样。
相同。dp[i][j]dp[i-1][j-1]
不同。省略了删除2个dp[i-1][j-1]2。dp[i][j]min(dp[i-1][j]1,dp[i][j-1]1)
