如何判断一个字符串是否是另一个字符串的子序列？（LeetCode 392）

简化版

判断 s 是否是 t 的子序列，用双指针：i 指向 s，j 指向 t。扫描 t，如果 s[i] == t[j]，说明匹配到一个字符，i++；无论是否匹配，j 都继续右移。最后如果 i == s.length()，说明 s 全部按顺序匹配成功。

详细版

boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
        if (s.charAt(i) == t.charAt(j)) {
            i++;
        }
        j++;
    }
    return i == s.length();
}

子序列不要求连续，只要求相对顺序不变。
指针 i 表示 s 已经匹配到的位置。
扫描 t 时可以跳过无关字符。
单次判断时间 O(|t|)，空间 O(1)。

完整版教学

一、子序列和子串的区别

子串必须连续，子序列可以删除若干字符但不能改变顺序。"ace" 是 "abcde" 的子序列，因为可以删除 b,d；但它不是子串，因为不连续。

这一区别决定了解法：子串匹配常用 KMP、滑动窗口、哈希；子序列判断只需要按顺序找字符，用双指针扫描即可。

二、双指针的含义

i 指向待匹配字符串 s 的下一个目标字符，j 指向母串 t 当前扫描位置。如果 s[i] == t[j]，就把 i 向右移动，表示这个目标字符已经被匹配；j 每轮都向右移动，因为 t 中每个字符最多使用一次。

s = ace
t = abcde
j 扫到 a -> i 从 0 到 1
j 扫到 c -> i 从 1 到 2
j 扫到 e -> i 从 2 到 3，匹配完成

记忆钩子：子序列判断是在 t 里按顺序“捡字符”，捡齐 s 就成功。

三、为什么贪心匹配最早出现的位置是正确的

当 t[j] 可以匹配 s[i] 时，选择最早的这个位置不会让后续更差。因为越早匹配当前字符，留给后续字符的 t 后缀越长，可选择空间越大。

如果跳过这个可匹配位置，去用后面另一个相同字符，后续可用范围只会变短，不会变长。因此“遇到就匹配”的贪心策略是安全的。

四、手推失败例子

s="aec"，t="abcde"：

匹配 a 成功，i 指向 e
t 继续扫 b、c、d，都不是 e
扫到 e，匹配成功，i 指向 c
t 已经结束，c 没有机会再匹配

虽然 t 中有 c，但它出现在 e 之前，顺序不符合，所以失败。这说明子序列不仅看字符是否存在，还看相对顺序。

五、多次查询时如何优化

如果只判断一次，双指针 O(|t|) 足够。如果有大量 s 要查询同一个 t，可以预处理 t 中每个字符出现的位置列表，然后对每个 s 用二分查找下一个大于当前位置的出现位置。

场景	做法	复杂度
单次查询	双指针扫描 t	O(
多个 s 查询同一个 t	预处理位置列表 + 二分	预处理 O(
小写字母且追求极致	next 数组自动机	预处理 O(26

面试若题目追加“有十亿个 s 要判断”，就要主动说预处理。

六、边界与复杂度

空字符串是任何字符串的子序列，所以 s="" 应返回 true。若 s.length() > t.length()，可以提前返回 false，因为母串字符数量不够。

双指针版本中，j 最多走完整个 t，i 最多走完整个 s，时间 O(|t|)，空间 O(1)。严格说循环次数不超过 t.length()。

七、常见误区与追问

误区：要求字符连续。 那是子串，不是子序列。
误区：只比较字符频次。 频次相同不代表顺序正确，例如 "aec" 不是 "abcde" 的子序列。
误区：匹配失败后回退 j。 子序列允许跳过 t 中字符，但不允许回头。
追问：空字符串是不是子序列？ 是，删除母串所有字符即可得到空串。
追问：大量查询怎么优化？ 预处理 t 的字符位置列表，用二分找每个字符的下一个位置。
追问：和编辑距离有什么区别？ 编辑距离允许插删改并求最小代价；子序列判断只问能否删除母串若干字符得到 s。

八、加强记忆

判断子序列 = 在 t 中按顺序捡齐 s。i 等待下一个要匹配的字符，j 扫描母串；遇到相等就 i++，j 永远向右。单次查询 O(|t|)，多次查询同一母串时再考虑位置列表或 next 自动机。

简化版

详细版