1 问题

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1

输入：s = “abc”, t = “ahbgdc”
输出：true

示例 2

输入：s = “axc”, t = “ahbgdc”
输出：false

提示：

0 <= s.length <= 100
0 <= t.length <= $10^4$
两个字符串都只由小写字符组成。

2 解题思路

2.1 贪心算法

逐位比较s和t的字符，

若$s_i$==$t_j$，则 i++;
j++

遍历完毕（依据是要么i==s.length，要么j==t.length），s正好遍历完毕，即 i=s.length，则证明s是t的子序列；否则便不是。

2.2 动态规划

2.2.1 定义dp

$dp_{ij}$ 表示，s[0,j] 是否是 t[0,i] 的子序列.

2.2.2 递进规则

若$s_j$==$t_i$，则只需要知道 s[0, j-1] 是否等于 t[0, i-1] 即可，即：
$dp_{ij}$ = $dp_{i-1, j-1}$

eg: t=”abcdsefgt”; s=”abst”;
假定现在已经遍历至 t[0,4]=”abcds”, s[0,2]=”abs”. 则$dp_{42}$ = $dp_{31}$. 即”abcd”是包含了”ab”的。应为 true.

否则，要判断 t[0, i-1]是否包含 s[0, j]，即：
$dp_{ij}$ = $dp_{i-1, j}$

同样的例子，当前 t[0,5]=”abcdse”, s[0,3]=”abst”, t[5]!=s[3]，则 $dp_{53}$ 的状态与 $dp_{43}$ 有关，即 “abcds” 是不包含 “abst”的。应为false。

3 代码

class Solution {
    //贪心算法
    public boolean isSubsequence1(String s, String t) {
        int i=0;
        int j=0;
        while(i<s.length() && j<t.length()){
            if(s.charAt(i)==t.charAt(j)){
                i++;
            }
            j++;
        }
        //如果s遍历完毕，则证明找到了，否则，没找到
        return i==s.length();
    }

    //动态规划
    public boolean isSubsequence(String s, String t) {
        //定义：dp[i][j]为s[0,j]是否为t[0,i]的子序列
        int sLen=s.length();
        int tLen=t.length();
        boolean[][] dp = new boolean[tLen+1][sLen+1];

        //若s为空串，则dp[i][0]全为true，空串肯定是t的子序列
        for(int i=0;i<=tLen;i++){
            dp[i][0]=true;
        }

        //规划
        for(int i=1;i<=tLen;i++){
            for(int j=1;j<=sLen;j++){
                //已经遍历的t的长度至少要比已经遍历的s的长度大
                if(i<j){
                    continue;
                }
                //相等，则dp[i][j]状态变更为dp[i-1][j-1];
                if(t.charAt(i-1)==s.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }
                //不等，则要看s[0,j]是否是t[0,i-1]的子序列
                else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[tLen][sLen];
    }
}