【代码随想录刷题记录】 392.判断子序列、 115.不同的子序列-Toy模板网

这篇具有很好参考价值的文章主要介绍了【代码随想录刷题记录】 392.判断子序列、 115.不同的子序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

392.判断子序列

1、题目
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

题目链接：https://leetcode.cn/problems/is-subsequence/

2、代码

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()];

    }
};