給定字符串 s 和 t 菩暗，判斷 s 是否為 t 的子序列朗若。
字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串太惠。（例如痕鳍，"ace"是"abcde"的一個子序列邪铲，而"aec"不是）芬位。
● 進階：
如果有大量輸入的 S，稱作 S1, S2, ... , Sk 其中 k >= 10億带到，你需要依次檢查它們是否為 T 的子序列昧碉。在這種情況下，你會怎樣改變代碼揽惹？

解題思路：動態(tài)規(guī)劃 / 貪心雙指針

1被饿、方式一：貪心雙指針

● 設(shè)置指向主序列 t 的指針 i，指向子序列 s 的指針 j搪搏。初始化** i = 0狭握，j = 0**
● 指針 i 一直遍歷主序列 t 后移；而對于指針 j 來說：只有當(dāng) t[i] == s[j] 時疯溺，j 指針才后移论颅；
?理解：t[i] 第一次和 s[j] 相等時哎垦，s[j] 就已經(jīng)匹配上了，就算主序列后面還有字母和它相等恃疯，也沒關(guān)系漏设。根據(jù)【貪心】，取最前面的一個今妄，萬一子序列后面還有一樣的需要主序列進行匹配呢郑口！
● 當(dāng) i >= t.length() || j >= s.length()，說明可以結(jié)束匹配盾鳞。
?此時如果 j == s.lenght() 說明 s 每個字母都匹配成功潘酗，s 是 t 的子序列；否則雁仲，s 不是 t 的子序列仔夺。

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length() == 0) return true;
        else if(t.length() == 0) return false;

        int j = 0;
        int i = 0;
        while(i < t.length() && j < s.length()){
            if(t.charAt(i) == s.charAt(j)) j++;
            i++;
        }
        if(j == s.length()) return true;
        else return false;
    }
}

2、方式二：動態(tài)規(guī)劃

(1) 定義dp數(shù)組
dp[i][j]：攒砖，以s[j]結(jié)尾的s序列 是否是 以t[i]結(jié)尾的t序列 的子序列缸兔。(boolean數(shù)組)

(2) 狀態(tài)轉(zhuǎn)移方程
? 注意：推導(dǎo) dp[i][j] 時，如果 dp[i-1][j] = true吹艇，此時 dp[i][j] 也一定為 true惰蜜！——這說明了 以s[j]結(jié)尾的s序列 已經(jīng)和 以 t[ i-1 ]結(jié)尾的t序列已經(jīng)匹配上了！

● 當(dāng) dp[ i-1 ][j] == true 時受神，dp[i][j] = true
● 當(dāng) dp[ i-1 ][j] == false 時
? ● dp[i][j] = dp[ i-1 ][ j-1 ] && (t[i] == s[j])

(3) 初始化
從狀態(tài)轉(zhuǎn)移方程可以看出抛猖，dp[i][j] 需要依賴 dp[ i-1 ][j]、dp[ i-1 ][ j-1 ]鼻听。
所以要單獨考慮 i == 0财著，及 j == 0 的情況：
● dp[0][0] = (t[i] == s[j])
● 當(dāng) i == 0，j != 0 時撑碴，dp[i][j] = false
● 當(dāng) i != 0撑教，j == 0 時，dp[i][j] = (t[i] == s[j])

(4) 遍歷順序
從上到下醉拓，從左到右

(5) 舉例：略

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length() == 0) return true;
        else if(t.length() == 0) return false;

        boolean[][] dp = new boolean[t.length()][s.length()];
        for(int i=0; i<t.length(); i++){
            for(int j=0; j<s.length(); j++){
                if(i == 0) dp[i][j] = (j == 0 && s.charAt(j) == t.charAt(i));
                else if(dp[i-1][j]) dp[i][j] = true;
                else if(j == 0) dp[i][j] = (s.charAt(j) == t.charAt(i));
                else {
                    dp[i][j] = dp[i-1][j-1] && s.charAt(j) == t.charAt(i);
                }
            }
            if(dp[i][s.length()-1]) return true;
        }
        return false;
    }
}

? 當(dāng)然伟姐，也可以套用最長公共子序列的動態(tài)規(guī)劃，看最后最長公共子序列是不是等于s.length()亿卤。

進階：大量子序列s

如果有大量輸入的 S愤兵，稱作 S1, S2, ... , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列排吴。在這種情況下秆乳，你會怎樣改變代碼？

上面 不管是用 貪心雙指針傍念，還是動態(tài)規(guī)劃矫夷，主序列 t 都要遍歷。
如果大量的子序列都要和同一個 t 比較憋槐，而 t 在這個過程中双藕，需要不斷地被遍歷處理，性能大大降低阳仔。
由于 主序列 t 是同一個忧陪，有沒有一種方法，可以對 t 處理一次近范，就能判斷 子序列 Si 是不是它的子序列嘶摊。

——當(dāng)匹配到某一點時，如果已知 【待匹配字母 在 主序列 t 中评矩，下一次出現(xiàn)的位置】叶堆，那么這個問題就很好解決了！
——假設(shè)主序列長度為n斥杜，創(chuàng)建一個 n*26 大小的矩陣虱颗，表示每一個下標位置上26個字符下一次出現(xiàn)的位置。

（1） 定義lastIndex二維數(shù)組蔗喂，用于研究主序列 t：
含義：lastIndex[i][j]：在主序列 t 中忘渔，當(dāng)前下標位置 i 對于字母j（0-25） 【下一次】出現(xiàn)的下標，如果以后都不出現(xiàn)缰儿，則為-1畦粮。
? 注意：要【從后往前】遍歷，因為要記錄下一次出現(xiàn)的下標乖阵。

int[][] lastIndex = new int[t.length()][26];
for(char c='a'; c<='z'; c++){
  int next = -1;
  for(int i=t.length()-1; i>=0; i--){
    lastIndex[i][c-'a'] = next;
    if(c == t.charAt(i)) next = i;
  }
}

（2）利用lastIndex數(shù)組宣赔，對子序列s，進行匹配
● curIndex：表示當(dāng)前【待匹配的 序列t 下標】（不可回頭）

int curIndex = 0; // 表示當(dāng)前【待匹配的 序列t 下標】（不可回頭）
int j = 0;
for(; j<s.length() && curIndex<t.length(); j++){
  int cIndex = s.charAt(j)-'a';
  if(t.charAt(curIndex) == s.charAt(j) || (curIndex = lastIndex[curIndex][cIndex]) != -1){ // 找 主序列t 中匹配的下標
    curIndex++;
  }else return false;
}

當(dāng)循環(huán)跳出的時候瞪浸，有兩種可能：
a) j >= s.length()拉背，說明子序列s 已經(jīng)全部匹配成功。
b) curIndex >= t.length()默终，說明主序列 t 已經(jīng)無法繼續(xù)找了椅棺，但是 s 還沒匹配完（j < s.length()），此時失敗齐蔽。

完整代碼：

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length() == 0) return true;
        else if(t.length() == 0) return false;

        // 先對主序列 t两疚，研究透徹
        // lastIndex[i][j]：在主序列 t 中，位置 i 對于字母j（0-25） 【下一次】出現(xiàn)的下標含滴，如果以后都不出現(xiàn)诱渤，則為-1
        int[][] lastIndex = new int[t.length()][26];
        for(char c='a'; c<='z'; c++){
            int next = -1;
            for(int i=t.length()-1; i>=0; i--){
                lastIndex[i][c-'a'] = next;
                if(c == t.charAt(i)) next = i;
            }
        }

        int curIndex = 0; // 表示當(dāng)前待匹配的 序列t 下標（不可回頭）
        int j = 0;
        for(; j<s.length() && curIndex<t.length(); j++){
            int cIndex = s.charAt(j)-'a';
            if(t.charAt(curIndex) == s.charAt(j) || (curIndex = lastIndex[curIndex][cIndex]) != -1){ // 找 主序列t 中匹配的下標
                curIndex++;
            }else return false;
        }
        
        if(j == s.length()) return true;
        else return false;
    }
}