怎样将自己做的网页加入网站,如何建立网站教程,河南网站建设制作,建设银行网站修改手机号码提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、不同的子序列二、两个字符串的删除操作三、编辑距离 前言
提示#xff1a;这里可以添加本文要记录的大概内容#xff1a;
今天是跟着代码随想录刷题的第… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、不同的子序列二、两个字符串的删除操作三、编辑距离 前言
提示这里可以添加本文要记录的大概内容
今天是跟着代码随想录刷题的第51天主要学习了不同的子序列、两个字符串的删除操作、编辑距离 提示以下是本篇文章正文内容下面案例可供参考
一、不同的子序列
思路 这道题的dp[i][j]是[0,i-1]的s最多能有多少种方式组合成[0,j-1],初始化dp[0][i]空字符串组成不了所以是0dp[i][0]是字符串中找多少个方式是空字符串那就是全部删除掉就可以了所以只有这一种至于dp[0][0]空字符串本身就是空字符串不用删减所以也是一种递推公式如果s[i-1]t[j-1]则dp[i][j]dp[i-1][j-1]dp[i-1][j]中 dp[i-1][j-1]是最后一个i来的时候一共多了多少种组合dp[i-1][j]是上一个有多少种组合所以合理如果最后一个元素不相等就说明加不加最后一个元素没区别直接等于dp[i-1][j] 代码
class Solution {
public:int numDistinct(string s, string t) {vectorvectoruint64_t dp(s.size()1,vectoruint64_t(t.size()1,0));for(int i0;is.size();i) dp[i][0]1;for(int i1;it.size();i) dp[0][i]0;for(int i1;is.size();i){for(int j1;jt.size();j){if(s[i-1]t[j-1]){dp[i][j]dp[i-1][j-1]dp[i-1][j];//dp[i-1][j-1]是最后一个i来的时候一共多了多少种组合dp[i-1][j]是上一个有多少种组合}else{dp[i][j]dp[i-1][j];}}}return dp[s.size()][t.size()];}
};
二、两个字符串的删除操作
思路 关键是dp数组的定义dp[i][j]表示[0,i-1]和[0,j-1]两个字符串如果要变成相同所需要的最小步数这里i-1和j-1是因为初始化比较简单递推公式推导见文中的注释 代码
class Solution {
public:int minDistance(string word1, string word2) {vectorvectoruint64_t dp(word1.size()1,vectoruint64_t(word2.size()1,0));//dp[i][j]表示[0,i-1]和[0,j-1]两个字符串如果要变成相同所需要的最小步数for(int i0;iword1.size();i)//初始化{dp[i][0]i;}for(int i0;iword2.size();i)//初始化{dp[0][i]i;}for(int i1;iword1.size();i){for(int j1;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,dp[i][j-1]1);//如果最后两个不一样就看到底是哪个变动需要的步数变动的那个把那行给去掉一个加上去掉需要的步数1}}}return dp[word1.size()][word2.size()];}
};
三、编辑距离
思路 如果最后两个不一样可能是增加删减或者替换先讲一下删除元素删除元素就是我要删除的那个元素不管上面缺一个元素i-1和下面j先操作操作完以后把上面那个元素删除就好了增加和删减其实一样因为我增加去迎合你是不是就相当于你减去一个迎合我的操作是一样的如果是替换那么我结尾的元素都不用管了把i-1,j-1的元素操作完成然后最后一对两个元素换成一样的一步骤就可以所以是dp[i-1][j-1]1
class Solution {
public:int minDistance(string word1, string word2) {vectorvectoruint64_t dp(word1.size()1,vectoruint64_t(word2.size()1,0));//dp[i][j]表示[0,i-1]和[0,j-1]两个字符串如果要变成相同所需要的最小步数for(int i0;iword1.size();i)//初始化{dp[i][0]i;}for(int i0;iword2.size();i)//初始化{dp[0][i]i;}for(int i1;iword1.size();i){for(int j1;jword2.size();j){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][j-1]1),dp[i-1][j-1]1);//如果最后两个不一样可能是增加删减或者替换}}}return dp[word1.size()][word2.size()];}
};
