代码随想录训练营第五十五天| ● 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.判断子序列?的区别。?

代码随想录