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

2023-12-14 14:57:28

目录

392 判断子序列

双指针法?

动态规划

115 不同的子序列

392 判断子序列

双指针法?

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int l = 0,r = 0;
        for(;l < t.size();l++){
            if(t[l] == s[r])r++;
        }
        if(r == s.size())return true;
        return false;
    }
};

时间复杂度O(n + m)

空间复杂度O(1)

动态规划

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>>dp(s.size() + 1,vector<int>(t.size() + 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] + 1;
                }else{
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[s.size()][t.size()] == s.size();
    }
};

时间复杂度O(n ×?m)

空间复杂度O(n × m)

115 不同的子序列

class Solution {
public:
    const int MOD = 1e9 + 7;
    int numDistinct(string s, string t) {
        vector<vector<int>>dp(s.size() + 1,vector<int>(t.size() + 1));//s的前i个字符中出现t的前j个字符的个数
        for(int i = 0;i < s.size();i++)dp[i][0] = 1;//s的前i个字符中均出现了空字符串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]) % MOD;
                }else{
                    dp[i][j] = dp[i - 1][j];//继承上次计算出来的值
                }
            }
        }
        return dp[s.size()][t.size()];
    }
};

时间复杂度O(n ×?m)

空间复杂度O(n × m)

文章来源:https://blog.csdn.net/m0_72832574/article/details/134978260
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。