392. 判断子序列

原题链接：392. 判断子序列

 

solution:

        动态规划：

状态表示：dp[i][j]:表示s的前i个字母是否是t的前j的字母的子序列
状态计算: 如果s[i] == t[j]则,dp[i][j] = dp[i - 1][j - 1]，否则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长度大于n一定不是子序列
        vector<vector<bool>> dp(m + 1, vector<bool> (n + 1, false)); 

        //dp[i][j]:表示s的前i个字母是否是t的前j的字母的子序列
        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];
    }
};

        双指针,只有s[j] == t[i],指针j才向后移动。

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;
    }
};