LeetCode 392. 判断子序列
题目描述
题意分析
判断是否能从字符串
t中删除若干字符，使剩余字符恰好组成s。保留下来的字符必须保持原有相对顺序，但不必连续，同一个位置只能使用一次。空字符串是任意字符串的子序列；只有
s的所有字符都按顺序找到才算成功。原题还要求考虑固定t、需要判断大量不同s的情形，下面补充一次预处理后批量查询的方法。
解法：双指针贪心匹配
核心思路
[!blue]
用
i指向s中下一个需要匹配的字符，用j从左到右扫描t。扫描期间，s[0..i-1]已经在t[0..j-1]中按顺序匹配完成。如果当前字符相等，就用
t[j]匹配s[i]，并推进i；不相等就跳过t[j]。无论是否匹配，j都前进一步，避免重复使用同一个文本位置。遇到相等字符时为什么可以立即使用？设某个可行方案用更靠后的相同字符匹配当前需求，把它替换成眼前这个更早位置后，后续匹配位置仍在它右边，原方案依然可行。选择最早位置只会给后续字符留下更多空间，不会丢掉任何解，所以不需要回溯。
当
i到达s末尾时已经成功；若t耗尽而i尚未到末尾，则剩余字符没有可用位置。空s在进入循环前就已全部匹配，返回条件自然得到true。
解题步骤
- 令
i = 0，表示还没有匹配s的任何字符。- 从左到右扫描
t，同时确保i < s.length()，避免访问已匹配完成的字符串。- 当前字符相等时令
i++，否则只继续扫描t。s匹配完或t扫描完后停止，返回i == s.length()。
代码实现
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的长度。文本指针最多前进 $m$ 次，模式指针只随匹配前进。- 空间复杂度：$O(1)$，只保存两个下标。
关键点总结
[!green]
- 子序列需要顺序一致，允许跳过文本字符，不能用子串查找或字符计数替代。
- 总选择最早可用位置，为剩余需求保留尽可能长的后缀。
i表示已匹配长度，只有命中才增加；文本位置每轮都要消耗。
进阶解法：预处理后继位置应对多次查询
核心思路
[!blue]
固定
t后反复扫描同一段文本，会产生大量重复工作。可以提前记录：从每个位置出发，下一个指定字符最早出现在哪里。输入只有小写字母，因此每个位置只需记录 26 种字符。令
next[pos][c]表示从pos开始、包含pos的后缀中，字符c第一次出现的下标。文本长度为m，用m表示不存在；额外创建第m行并全部填为m，代表空后缀。从右向左建立表。先把后一行复制到当前行，因为除当前位置的字符外，其他字符的最早位置都不变；再令
next[pos][t[pos]] = pos，让当前字符指向自己。查询一个
s时，从pos = 0开始，逐字符直接查出最早可用位置。查到m说明没有匹配，立即失败；否则令pos = found + 1，保证下一个字符只使用其后的文本。匹配策略与双指针完全相同，只是把扫描过程压缩成一次查表。下方查询器创建时只接收固定文本并预处理一次，之后每次传入一个模式进行判断。模式可以逐条处理，不必把海量查询或全部结果同时保存在内存中。
解题步骤
- 创建
(m + 1) × 26的后继表，将空后缀的全部后继设为m。- 从文本末尾向前复制后一行，并更新当前字符的最早下标。
- 对每个模式从位置零开始，逐字符查询后继；找到后移动到其下一位。
- 任一字符没有后继则该模式失败；全部字符找到则成功。
代码实现
class SubsequenceMatcher {
private final int[][] next;
public SubsequenceMatcher(String t) {
int m = t.length();
next = new int[m + 1][26];
for (int c = 0; c < 26; c++) {
next[m][c] = m;
}
for (int pos = m - 1; pos >= 0; pos--) {
System.arraycopy(next[pos + 1], 0, next[pos], 0, 26);
next[pos][t.charAt(pos) - 'a'] = pos;
}
}
public boolean isSubsequence(String s) {
int m = next.length - 1;
int pos = 0;
for (int i = 0; i < s.length(); i++) {
int found = next[pos][s.charAt(i) - 'a'];
if (found == m) {
return false;
}
pos = found + 1;
}
return true;
}
}
type SubsequenceMatcher struct {
next [][26]int
}
func NewSubsequenceMatcher(t string) *SubsequenceMatcher {
m := len(t)
next := make([][26]int, m+1)
for c := 0; c < 26; c++ {
next[m][c] = m
}
for pos := m - 1; pos >= 0; pos-- {
next[pos] = next[pos+1]
next[pos][t[pos]-'a'] = pos
}
return &SubsequenceMatcher{next: next}
}
func (matcher *SubsequenceMatcher) IsSubsequence(s string) bool {
m := len(matcher.next) - 1
pos := 0
for i := 0; i < len(s); i++ {
found := matcher.next[pos][s[i]-'a']
if found == m {
return false
}
pos = found + 1
}
return true
}
复杂度分析
- 时间复杂度：$O(26m+q+L)$，其中 $m$ 为文本长度，$q$ 为模式个数，$L$ 为模式总长度。预处理为 $O(26m)$，每个模式字符至多查询一次，查询可以逐条输入。
- 空间复杂度：$O(26m)$，保存全部查询共享的后继表；每次查询额外只使用常数空间。
关键点总结
[!green]
- 双指针每次寻找的都是最早后继，可以将这一步提前制表。
- 第
m行统一处理文本已用完的情况，避免越界和特殊分支。- 查到字符后从下一位继续，保证同一个文本位置最多使用一次。
- 单次判断用双指针即可，大量模式共用一个文本时才适合这份预处理。
易错点总结
[!yellow]
- 匹配后只推进
i而不推进文本位置，会把同一个字符重复使用。- 只比较字符频次会丢失相对顺序，无法判断子序列。
- 成功条件是
s已匹配完，不是t已扫描完。- 空模式应返回
true；后继表查询也要允许从位置m开始查询，并用哨兵表示找不到。- 多次查询只共享文本预处理，每个新模式的匹配位置必须重新从零开始。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 522. 最长特殊序列 II | 中等 | 该题逐个检查候选字符串是否为其他字符串的子序列，可直接复用本题双指针匹配；只在外层增加候选枚举与长度筛选。 |