判断子序列

392. 判断子序列

给定字符串 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.

最直观的办法就是维护两个指针，判断子序列中的所有字符是否在原始字符串中。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i=0, j=0;
        for(;i<t.length() && j<s.length();++i){
            if(t.charAt(i) == s.charAt(j)){
                ++j;
            }
        }
        //子字符串被全部匹配
        return j == s.length();
    }
}

时间复杂度O(n)，空间复杂度O(1)。

双指针解法中有大量的时间用于在 t 中找到下一个匹配字符。我们预处理出对于 t 的每一个位置，从该位置开始往后的每种字符第一次出现的位置。

令f[i][j]表示字符串 t 从位置 i 开始往后字符 j 第一次出现的位置。在进行状态转移时，如果 t 中位置 i 的字符就是 j ，那么f[i][j] = i，否则 j 出现在位置 i + 1开始往后，即f[i][j] = f[i + 1][j]，我们从后往前进行动态规划，得到状态转移方程：
$$f[i][j]=i,t[i]=j$$

$$f[i][j]=f[i+1][j],t[i]\ne j$$

假设下标从 0 开始，那么 f[i][j]中有 0 <= i <= m - 1，对于边界条件 f[m - 1][...]，我们置 f[m][...] = m，让f[m - 1][...]进行正常转移。

我们利用 f 数组，每次O(1)地跳转到下一个位置。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();
        int[][] f = new int[m + 1][26];
        //边界条件
        for(int i = 0; i < 26; i++){
            f[m][i] = m;
        }
		//生成 dp 数组
        for(int i = m - 1; i >= 0; i--){
            for(int j = 0; j < 26; j++){
                if(t.charAt(i) == j + 'a')
                    f[i][j] = i;
                else
                    f[i][j] = f[i + 1][j];
            }
        }
        //从头部开始查看 s 是是 t 的子序列
        int add = 0;
        for(int i = 0; i < n; i++){
            if(f[add][s.charAt(i) - 'a'] == m){
                return false;
            }
            add = f[add][s.charAt(i) - 'a'] + 1;
        }

        return true;
    }
}

时间复杂度O(m * 26 + n)，其中 n 为 s 的长度，m 为 t 的长度。

空间复杂度O(m * 26)。