判断子序列

 1   //dp解法
 2     bool isSubsequence(string s, string t){
 3         int n = s.length(),m = t.length();
 4         //dp数组dp[i][j]表示字符串t以i位置开始第一次出现字符j的位置
 5         vector<vector<int>> dp(m + 1,vector<int> (26,0));
 6 
 7         //初始化边界条件，dp[i][j] = m表示t中不存在字符j
 8         for(int i=0;i<26;i++){
 9             dp[m][i] = m;
10         }
11 
12         //从后往前递推初始化dp数组
13         for(int i = m - 1;i>=0;i--) {
14             for(int j=0;j<26;j++){
15                 if(t[i] == ‘a‘ + j){
16                     dp[i][j] = i;
17                 }else {
18                     dp[i][j] = dp[i + 1][j];
19                 }
20             }
21         }
22 
23         int add = 0;
24         for(int i = 0;i<n;i++){
25             //t中没有s[i] 返回false
26             if(dp[add][s[i] - ‘a‘] == m){
27                 return false;
28             }
29             //否则直接跳到t中s[i]第一次出现的位置之后一位
30             add = dp[add][s[i] - ‘a‘] + 1;
31         }
32         return true;
33     }