392.判断子序列
1、题目
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
题目链接:https://leetcode.cn/problems/is-subsequence/
2、代码文章来源:https://www.toymoban.com/news/detail-575230.html
class Solution {
public:
bool isSubsequence(string s, string t) {
if(t.size() < s.size()) return false;
//定义dp数组,dp[i][j]表示0-i中0-j公共子序列的长度
vector<vector<int>> dp(t.size() + 1, vector<int>(s.size() + 1, 0));
//初始化
for(int i = 1; i <= t.size(); i++){
for(int j = 1; j <= s.size(); j++){
if(t[i - 1] == s[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i - 1][j];
}
}
if(dp[t.size()][s.size()] == s.size()) return true;
return false;
}
};
3、小结
使用dp数组计算两个字符串最长公共子序列的长度,如果该长度与s的长度相等就说明s是t的子序列。
115.不同的子序列
1、题目
给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数。
题目链接:https://leetcode.cn/problems/distinct-subsequences/
2、代码
class Solution {
public:
int numDistinct(string s, string t) {
//特殊情况
if(s.size() < t.size()) return 0;
//定义dp数组
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));
//dp数组初始化
for(int i = 0; i <= s.size(); i++){
dp[i][0] = 1;
}
//遍历
for(int i = 1; i <= s.size(); i++){
for(int j = 1; j <= t.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()];
}
};
3、小结
使用dp数组记录当前情况下s包含的t的个数,遇到s[i-1]==t[i-1]时有两种情况一个是使用s[i-1],一个是不使用s[i-1]。本题的重点就是该种情况下递推公式的确定。文章来源地址https://www.toymoban.com/news/detail-575230.html
到了这里,关于【代码随想录刷题记录】 392.判断子序列 、 115.不同的子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!