力扣 392. 判断子序列

题目来源：https://leetcode.cn/problems/is-subsequence/description/

C++题解1：在t中按顺序一个一个寻找s的元素。

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

C++题解2（来源代码随想录）：动态规划。虽然这样复杂好多，但是原网址说是为了后续的学习打下基础。

1. 确定dp数组（dp table）以及下标的含义。dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
2. 确定递推公式。在确定递推公式的时候，首先要考虑如下两种操作，整理如下：

• if (s[i - 1] == t[j - 1])：t中找到了一个字符在s中也出现了
• if (s[i - 1] != t[j - 1])：相当于t要删除元素，继续匹配

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        if(m == 0) return true;
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        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] + 1;
                else dp[i][j] = dp[i][j-1];
            }
        }
        if(dp[m][n] == m) return true;
        else return false;
    }
};