题目描述

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

后续挑战:

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

算法1

(贪心+双指针扫描) $O(m + n)$

对于s串的每个字母，我们只需要找到t中该字母出现的第一个位置，因为如果t中还有相同的字母，那么后面的位置一定不优于当前的位置，所以我们用双指针来进行贪心的匹配，将t串遍历一遍，中间遇到与当前s串相同的字母就将s串的指针后移，最后看能不能完全匹配s串。

时间复杂度

假设s串和t串的长度分别是 $m$ 和 $n$ ，时间复杂度为 $O(m + n)$ 。

C++ 代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int j = 0;
        for (int i = 0; i < t.size(); i ++ ) {
            if (j < s.size() && s[j] == t[i]) {
                j ++ ;
                if (j == s.size()) return true;
            }
        }
        return j == s.size();
    }
};

算法2

(预处理) $O(26 * n + m)$

这道题的 follow-up 是假设t串很长，然后有很多个s串要匹配，算法1每次都要扫描一遍t串，效率比较低。这里我们采用预处理的方法，可以在$O(26 * n)$ 的时间内构建出一个数据结构f[n][26]（也可以开成f[26][n]，含义是一样的），这里f[i][j]代表着在t串的i位置（从0开始）后（包括该位置）每个字符第一次出现的位置，以字符串"ahbgdc"举例，f[0][0] = 0代表着在第0个位置后字母a第一次出现的位置是0，我们将f[i][j]初始化为-1代表着开始每个字符都不存在。

注意到如果我们从前往后构造f需要花费 $O(n^2)$ 的时间（从0开始扫描n个字符，从1开始扫描n - 1个字符…），所以我们从后往前构造f，每次将前一个位置构造好的数组复制过来再更新当前位置，总时间 $O(26 * n)$ ，这里26是字母表的大小。

C++ 代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = t.size();
        // 这里f多开一维方便处理边界
        vector<vector<int>> f(n + 1, vector<int>(26, -1));
        for (int i = n - 1; i >= 0; i -- ) {
            f[i] = f[i + 1];
            f[i][t[i] - 'a'] = i;
        }
        int idx = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            if (f[idx][s[i] - 'a'] == -1) return false;
            idx = f[idx][s[i] - 'a'] + 1;
        }
        return true;
    }
};