【第55天|● 392.判断子序列 ● 115.不同的子序列 】

392.判断子序列

class Solution {
public:bool isSubsequence(string s, string t) {if(s.size()==0)return true;if(t.size()==0) return false;vector<bool> dp(t.size()+1, true);for(int i=0; i<s.size(); i++){for(int j=t.size(); j>0; j--){if(s[i]==t[j-1]&&dp[j-1]==true){dp[j]=true;}else{dp[j] = false;}}for(int i=2; i<=dp.size(); i++){if(dp[i-1]) dp[i]=true;cout<<dp[i];}cout<<endl;}return dp[t.size()];}
};

115.不同的子序列

class Solution {
public:int numDistinct(string s, string t) {vector<vector<unsigned int >> dp(t.size()+1, vector<unsigned int>(s.size()+1, 0));for(int i=0;i<=s.size(); i++){dp[0][i] =1;}for(int i=1; i<=t.size(); i++){for(int j=1; j<=s.size(); j++){if(s[j-1]==t[i-1]) dp[i][j]=dp[i-1][j-1]+dp[i][j-1];else if(s[j-1]!=t[i-1]) dp[i][j] = dp[i][j-1];}}return dp[t.size()][s.size()];}
};

class Solution {//一维数组逆序滚动实现
public:int numDistinct(string s, string t) {vector<unsigned int > dp(t.size()+1);dp[0] = 1;for(int i=0; i<s.size(); i++)//先遍历背包{for(int j=t.size(); j>0; j--)//注意这里要逆序{if(s[i]==t[j-1]) dp[j] = dp[j] + dp[j-1];}}return dp[t.size()];}
};