392.md

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

后续挑战 :

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

---

解法一：双指针
思路：

本题询问的是，$s$ 是否是 $t$ 的子序列，因此只要能找到任意一种 $s$ 在 $t$ 中出现的方式，即可认为 $s$ 是 $t$ 的子序列。

而当我们从前往后匹配，可以发现每次贪心地匹配靠前的字符是最优决策。

假定当前需要匹配字符 $c$，而字符 $c$ 在 $t$ 中的位置 $x_1$ 和 $x_2$ 出现（$x_1 < x_2$），那么贪心取 $x_1$ 是最优解，因为 $x_2$ 后面能取到的字符，$x_1$ 也都能取到，并且通过 $x_1$ 与 $x_2$ 之间的可选字符，更有希望能匹配成功。

这样，我们初始化两个指针 $i$ 和 $j$，分别指向 $s$ 和 $t$ 的初始位置。每次贪心地匹配，匹配成功则 $i$ 和 $j$ 同时右移，匹配 $s$ 的下一个位置，匹配失败则 $j$ 右移，$i$ 不变，尝试用 $t$ 的下一个字符匹配 $s$。

最终如果 $i$ 移动到 $s$ 的末尾，就说明 $s$ 是 $t$ 的子序列。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = s.length();
        int m = t.length();
        int left = 0;
        int right = 0;
        while (left < n && right < m) {
            if (s.charAt(left) == t.charAt(right)) {
                left++;
            }
            right++;
        }
        return left == n;
    }
}

复杂度分析：

• 时间复杂度：$O(n+m)$，其中 $n$ 为 $s$ 的长度，$m$ 为 $t$ 的长度。每次无论是匹配成功还是失败，都有至少一个指针发生右移，两指针能够位移的总距离为 $n+m$。
• 空间复杂度：$O(1)$。