392. Judgement subsequence

Original link ：392. Judging subsequences

 

solution:

        Dynamic programming ：

State means ：dp[i][j]: Express s Before i Are the letters yes t Before j Subsequence of letters of
State calculation : If s[i] == t[j] be ,dp[i][j] = dp[i - 1][j - 1], otherwise dp[i][j] = dp[i][j - 1]

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(),n = t.size();
        if(m > n) return false; //m Longer than n It must not be a subsequence 
        vector<vector<bool>> dp(m + 1, vector<bool> (n + 1, false)); 

        //dp[i][j]: Express s Before i Are the letters yes t Before j Subsequence of letters of 
        for(int i = 0;i <= n;i++) dp[0][i] = true;

        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                if(s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

        Double pointer , Only s[j] == t[i], The pointer j To move backwards .

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(),n = t.size();
        if(!m) return true;
        if(m > n) return false;
        for(int i = 0,j = 0;i < n;i++) {
            if(s[j] == t[i]) j++;
            if(j == m) return true;
        }
        return false;
    }
};