题目

题解

dp[i][j]保存的是在长字符串t中 i 位置后 j+’a’ 出现的位置 ；
如果 t[i] = j+’a’ ： 那就是说明t的i位置上的字符就是j+’a’ , 那么 dp[i][j] = i ;
否则的话就是 dp[i][j] = dp[i + 1][j]; 意思是t的i+1 后面出现的 j 就是 t的 i 后面出现的 j 。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int tl = t.size();
        int sl = s.size();
        vector<vector<int>> dp(tl + 1, vector<int>(26, 0));
        //设置从最后开始，最后的数以后出现的位置都为tl
        for (int i = 0 ; i < 26; i++) {
            dp[tl][i] = tl;
        }
        //从后往前进行规划填表
        for (int i = tl - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t[i] == j + 'a') {
                    dp[i][j] = i;
                }
                else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        int add = 0;
        //进行查表从前往后，如果为tl说明该字符在t中没有（开始在最后就设置了）
        for (int i = 0; i < sl; i++) {
            if (dp[add][s[i] - 'a'] == tl) {
                return false;
            }
            //有的话就从该位置进行 
            add = dp[add][s[i] - 'a']+1;
        }
        return true;
    }
};