学院网站建设时间控制变更申请表,企业网站怎么做产品图片轮播,苏州建设厅网站,西安注册公司网上核名● 583. 两个字符串的删除操作
这道题涉及到两个字符串删除操作#xff0c;注意递推公式#xff0c;理解不到位#xff0c;需要再次做
确定dp数组#xff08;dp table#xff09;以及下标的含义
dp[i][j]#xff1a;以i-1为结尾的字符串word1#xff0c;和以j-1位结尾…● 583. 两个字符串的删除操作
这道题涉及到两个字符串删除操作注意递推公式理解不到位需要再次做
确定dp数组dp table以及下标的含义
dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。
这里dp数组的定义有点点绕大家要撸清思路。
确定递推公式
当word1[i - 1] 与 word2[j - 1]相同的时候当word1[i - 1] 与 word2[j - 1]不相同的时候
当word1[i - 1] 与 word2[j - 1]相同的时候dp[i][j] dp[i - 1][j - 1];
当word1[i - 1] 与 word2[j - 1]不相同的时候有三种情况
情况一删word1[i - 1]最少操作次数为dp[i - 1][j] 1
情况二删word2[j - 1]最少操作次数为dp[i][j - 1] 1
情况三同时删word1[i - 1]和word2[j - 1]操作的最少次数为dp[i - 1][j - 1] 2
那最后当然是取最小值所以当word1[i - 1] 与 word2[j - 1]不相同的时候递推公式dp[i][j] min({dp[i - 1][j - 1] 2, dp[i - 1][j] 1, dp[i][j - 1] 1});
因为 dp[i][j - 1] 1 dp[i - 1][j - 1] 2所以递推公式可简化为dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1);
这里可能不少录友有点迷糊从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1]dp[i][j-1] 本来就不考虑 word2[j - 1]了那么我在删 word1[i - 1]是不是就达到两个元素都删除的效果即 dp[i][j-1] 1。
dp数组如何初始化
从递推公式中可以看出来dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。
class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。vectorvectorint dp(word1.size()1,vectorint (word2.size()1,0));for(int i 0;iword1.size()1;i){dp[i][0] i;}for(int j 0;jword2.size()1;j){dp[0][j] j;}for(int i 1;iword1.size();i){for(int j 1;jword2.size();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][j-1]1,dp[i-1][j-1]2));}}}return dp[word1.size()][word2.size()];}
};
● 72. 编辑距离
这道题和之前讲的三四道题类似都是一步一步递增的之后需要继续看
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size()1,vectorint(word2.size()1,0));for(int i 0;iword1.size();i) dp[i][0] i;for(int j 0;jword2.size();j) dp[0][j] j;for(int i 1;iword1.size();i){for(int j 1;jword2.size();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],min(dp[i][j-1],dp[i-1][j-1]))1;}}}return dp[word1.size()][word2.size()];}
}; ● 编辑距离总结篇
1.判断子序列
if (s[i - 1] t[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;
else dp[i][j] dp[i][j - 1];
2.不同的子序列
if (s[i - 1] t[j - 1]) {dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];
} else {dp[i][j] dp[i - 1][j];
}
3.两个字符串的删除操作
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] 2, dp[i - 1][j] 1, dp[i][j - 1] 1});
}
4.编辑距离
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 - 1][j], dp[i][j - 1]}) 1;
}
