LeetCode 392. 判断子序列
目录
题目描述
题意分析
输入两个字符串
s和t，输出一个布尔值：能否从t中删除若干个（可以是零个）字符，且不改变剩余字符的相对顺序，恰好得到s。「不改变相对顺序」和「可以不连续」这两点合起来，把子序列和子串区分开了。
"abc"是"ahbgdc"的子序列，却不是它的子串；反过来，"ba"里两个字符虽然都在"ab"中出现过，但顺序不对，所以不是子序列。这也说明只统计字符出现次数是不够的，判定必须带上位置信息。数据规模上，
s很短（长度不超过 100），t很长（长度可达 $10^4$），这个不对称提示我们：算法的开销应该由t的一次扫描主导，不应该出现对t的反复回退或重复扫描。需要单独确认的边界：
s为空串时答案恒为 true，因为空串是任何字符串的子序列（删光所有字符即可）；t为空而s非空时恒为 false；s比t长时必然 false；s中含重复字符时，每一个都必须在t中找到各自独立的一个位置，不能共用同一个下标。最后是进阶要求：如果有大量（例如 $10^9$ 个）不同的
s，需要依次判断它们是不是同一个t的子序列，该怎么办。此时t是固定不变的，而每来一个s就重扫一遍长长的t，总开销会被查询次数放大到无法接受。既然被查询的对象固定，就应该对t做一次预处理，把「从某个位置往后，某个字符下一次出现在哪里」这件事提前算好并存下来，之后每个查询只需要沿着s的长度跳几步，与t的长度脱钩。这是本题从简单题变成考点题的地方，具体做法见下文核心思路的末尾。
解法：双指针贪心匹配
核心思路
用指针
i指向s中下一个待匹配字符，指针j从左到右扫描t。字符相等时同时前进，否则只移动j。贪心选择
t中最早能匹配s[i]的位置是安全的：若某个更晚的位置能形成合法答案，把它替换成当前更早的位置，只会为后续字符留下更长的后缀，不会破坏原有匹配。因此不需要回溯或动态规划。循环不变量是：
s的前i个字符已经按顺序匹配到t的已扫描前缀，并且占用的是尽可能靠左的位置。最终i走到s.length()，就说明全部匹配成功。
解题步骤
- 初始化
i = 0，从头扫描t。- 若
s[i] == t[j]，说明找到当前字符最早的可用位置，令i++。- 无论是否匹配，
j都要前进，因为当前位置已经使用或已经确认无用。- 当
s匹配完或t扫描完时停止，返回i == s.length()。例如
s = "abc"、t = "ahbgdc"，依次在t的下标 0、2、5 找到a、b、c，所以返回true。
代码实现
class Solution {
public boolean isSubsequence(String s, String t) {
int i = 0;
for (int j = 0; i < s.length() && j < t.length(); j++) {
if (s.charAt(i) == t.charAt(j)) {
i++;
}
}
return i == s.length();
}
}
func isSubsequence(s string, t string) bool {
i := 0
for j := 0; i < len(s) && j < len(t); j++ {
if s[i] == t[j] {
i++
}
}
return i == len(s)
}
复杂度分析
- 时间复杂度：$O(m)$，其中 $m$ 是
t的长度；扫描指针从不回退。- 空间复杂度：$O(1)$，只使用下标变量。
关键点总结
- 子序列要求顺序一致但不要求连续，不能用子串查找或字符计数代替。
- 每次取最早匹配位置，为后续字符保留的空间最大，这是贪心正确性的依据。
t的指针每轮都前进，s的指针只在匹配时前进。- 若大量查询共享同一个
t，可预处理每个字符的出现位置，再用二分查找完成单次查询。
易错点总结
- 匹配成功后只移动
i，会让同一个t[j]被重复使用。- 用字符频次判断会忽略相对顺序，例如
ba不是ab的子序列。- 返回条件应判断
s是否匹配完，而不是t是否扫描完。- 空字符串是任何字符串的子序列，现有循环无需额外特判即可正确处理。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 115. 不同的子序列 | 困难 | 子序列出现次数计数 |
| 524. 通过删除字母匹配到字典里最长单词 | 中等 | 子序列判定加字典序择优 |
| 792. 匹配子序列的单词数 | 中等 | 同一主串的多串查询预处理 |
| 1143. 最长公共子序列 | 中等 | 二维动态规划 |