題目

給定字符串 s 和 t ，判斷 s 是否為 t 的子序列见妒。

你可以認為 s 和 t 中僅包含英文小寫字母。字符串 t 可能會很長（長度 ~= 500,000）或详，而 s 是個短字符串（長度 <=100）。

字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串溶褪。（例如器仗，"ace"是"abcde"的一個子序列爬泥，而"aec"不是）晶姊。

示例 1:
s = "abc", t = "ahbgdc"

返回 true.

示例 2:
s = "axc", t = "ahbgdc"

返回 false.

后續(xù)挑戰(zhàn) :

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/is-subsequence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有砍艾。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處巍举。

解法1：自己做的

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length()==0){
            return true;
        }
        int j = 0 ;
        for(int i = 0 ; i < t.length();i++){
           
            if(s.charAt(j)==t.charAt(i)){
                j++;
            }
           
            if(j==s.length()){
                return true;
            }
        }
        return false;
    }
}

解法2：動態(tài)規(guī)劃

class Solution {
    public boolean isSubsequence(String s, String t) {
        int  slen=s.length();
        int  tlen=t.length();
        int[][] dp=new int[slen+1][tlen+1];
        if(slen==0){
            return true;
        }
        if(tlen==0){
            return false;
        }
        for(int i = 0; i <tlen; i++){
            dp[0][i]=1;
        }
        for(int i = 1 ; i <=slen; i++){
            for(int j = 1 ; j <=tlen; j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=dp[i][j-1];
                }
            }
        }
        return dp[slen][tlen]==1;
    }
}

寫的出來狀態(tài)轉(zhuǎn)移方程很重要脆荷，然后再依據(jù)方程初始化備忘本，然后遞推下去。