微信网站建设报价表,男生做网站运营的前景,邢台太行中学简介,人事管理软件不同的子序列
给定一个字符串 s 和一个字符串 t #xff0c;计算在 s 的子序列中 t 出现的个数。、
编辑距离中的删除元素#xff0c;其实就是直接变数字#xff0c;其只删除原来的较长的数组里的元素
递推模拟#xff0c;使用s的最后一个元素匹配#xff0c;或者删除…不同的子序列
给定一个字符串 s 和一个字符串 t 计算在 s 的子序列中 t 出现的个数。、
编辑距离中的删除元素其实就是直接变数字其只删除原来的较长的数组里的元素
递推模拟使用s的最后一个元素匹配或者删除最后一个元素看前面一个是否匹配
初始化dp[i][0]1表示s不为空t为空这样把s删到空就一定有一个同理dp[0][i]0,重叠部分dp[0][0]就等于空字符串匹配空字符串为1 定义为int出现了超时错误 所以可以用longlongint 的别名 uint64_t
class Solution {
public:int numDistinct(string s, string t) {vectorvectoruint64_t dp(s.size()1,vectoruint64_t(t.size()1));for(int i0;is.size();i) dp[i][0]1;for(int j1;jt.size();j) dp[0][j]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];}else{dp[i][j]dp[i-1][j];}}}return dp[s.size()][t.size()];}
};两个字符串的删除操作
其实就是两个字符串都可以删除了
递推公式如下
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size()1,vectorint(word2.size()1));for(int i0;iword1.size();i) dp[i][0]i;for(int j0;jword2.size();j) dp[0][j]j;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);}}return dp[word1.size()][word2.size()];}
};思路二是先求出公共子序列的长度再用两个字符串的总长度减去公共子序列的长度
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size()1, vectorint(word2.size()1, 0));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] 1;else dp[i][j] max(dp[i-1][j], dp[i][j-1]);}}return word1.size()word2.size()-dp[word1.size()][word2.size()]*2;}
};
编辑距离动规经典问题 为什么这道题不能采用上一题的思路二先求出公共子序列的长度再用两个字符串的总长度减去公共子序列的长度因为很可能长度一样但可以只替换一次就完成但思路2会要求按着顺序删除
