代码随想录训练营第五十五天| ● 392.判断子序列 ● 115.不同的子序列

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.判断子序列 的区别。 

代码随想录