本文主要是介绍代码随想录算法训练营第五十四天| 392 判断子序列 115 不同的子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
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)
这篇关于代码随想录算法训练营第五十四天| 392 判断子序列 115 不同的子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
