代码随想录训练营第五十五天| ● 392.判断子序列 ● 115.不同的子序列
2024-01-03 16:07:17
392.判断子序列?
这道题目算是?编辑距离问题?的入门题目(毕竟这里只是涉及到减法),慢慢的,后面就要来解决真正的?编辑距离问题了
与之前1143.最长公共子序列类似,只不过那道题是求两个字符串的公共子序列,这个是判断一个短的字符串是否是另一个字符串的子序列,因此区别就在于当遍历到两字符串不相同的元素时,这道题只会将长的字符串的该元素跳过,子序列的该元素并不会跳过,即dp[i][j] = dp[i][j-1];
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
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] + 1;
}
else {
dp[i][j] = dp[i][j-1];
}
}
}
if (dp[s.size()][t.size()] == s.size())
return true;
return false;
}
?115.不同的子序列?
但相对于刚讲过?392.判断子序列,本题?就有难度了?,感受一下本题和??392.判断子序列?的区别。?
文章来源:https://blog.csdn.net/Ljhh_h/article/details/135354358
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!