class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size()==0&&t.size()!=0) return true;
        if(s.size()==0&&t.size()==0) return true;
        if(s.size()!=0&&t.size()==0) return false;
        vector<bool> dp(s.size() , false);
        int prt = 0;//匹配指针
        for(int i=0 ; i<t.size() ;i++)
        {
            if(s[prt] == t[i])//匹配成功标记，匹配下一个
            {
                dp[prt] = true;
                prt++;
            }
        }
        return dp[s.size()-1];
    }
};

class Solution {
public:
    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] = max(dp[i-1][j] , dp[i][j-1]);
                // cout<<dp[i][j]<<' ';
            }
            // cout<<endl;
        }
        if(dp[s.size()][t.size()] == s.size()) 
            return true;
        else 
            return false;
    }
};