392. 判断子序列（Is Subsequence）
难度：简单 | 主题：字符串——双指针贪心
题目
给定字符串 s 和 t，判断 s 是否为 t 的子序列。子序列不要求连续，但要求相对顺序一致。
示例：
s = "abc", t = "ahbgdc" → True（'a'、'b'、'c' 按顺序出现）
s = "axc", t = "ahbgdc" → False
思路
先讲个故事：朋友圈的点赞记录
你翻看一个人的朋友圈，想找他有没有在特定几天发过帖。你手里有一串日期清单（s），朋友圈是时间线（t）。
你不会乱翻——你按时间线从头扫，每看到一个匹配的日期就打个勾。如果所有日期都勾完了，说明这人确实在那些天发过帖。
这就是双指针贪心：s 的每个字符都要在 t 中按顺序找到匹配。
引导式推导：从暴力到双指针
第 1 层：暴力 O(n×m)
对 s 的每个字符，在 t 中从头找匹配。
第 2 层：双指针 O(n)
i 指向 s，j 指向 t。如果 s[i] == t[j]，i++；无论是否匹配，j++。最后看 i 是否走完了 s。
graph LR subgraph 双指针匹配 A["i 指向 s<br/>j 指向 t"] --> B{"s[i] == t[j]?"} B -->|是| C["i++, j++"] B -->|否| D["j++ only"] C --> E{"i == len(s)?"} D --> E E -->|是| F["True"] E -->|否| A end
为什么贪心成立？ s 的每个字符只需要在 t 中找到第一个匹配即可。越早匹配，留给后面字符的空间越大。
代码
def isSubsequence(self, s, t):
i = 0
j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n) | n 是 t 的长度，每个字符最多访问一次 |
| 空间 | O(1) | 只用了两个指针 |
实战考量
频率分析
简单但高频，约 20% 考察双指针基本功。很多场景用到子序列判断（如日志匹配）。
延伸思考
Q：如果有很多个 s 需要判断呢？
A：预处理 t，对每个字符记录它后面每个字符的下一个位置（二分查找优化到 O(m log n)）。
Q：如果 t 是数据流（只能读一次）呢？
A：只能在线贪心匹配，无法预处理。
Q：最长公共子序列怎么做？
A：动态规划，二维 DP（1143最长公共子序列）。
易错点
-
j每次都要前进，i只在匹配时前进 -
返回值是
i == len(s)不是j == len(t) -
空串是任何串的子序列
生活类比
朋友圈点赞记录 → 贪心匹配
你按时间线从头扫，每看到一个匹配的日期就打个勾。
不需要回头找——如果这个日期错过了，后面的更不可能匹配上。
贪心的本质：按顺序，不回头。
相关题目
| 题目 | 关系 |
|---|---|
| 1143最长公共子序列 | LCS 基础，DP 版 |
| 72编辑距离 | 字符串编辑系列 |
| 521最长特殊子序列 | 子序列变体 |
→ 返回题单：LeetCode学习路线图 > 二、字符串
速记卡（面试闪卡）
Q1：一句话讲清「392. 判断子序列（Is Subsequence）」到底是什么？
A：判断字符串 s 是否按原顺序出现在 t 中，双指针贪心一遍扫即可。
Q2：题目理解 —— 什么算子序列？ —— 怎么理解？
A：像在朋友圈时间线里找特定几天的点赞：不要求连续，但先后顺序不能乱。s 是清单，t 是时间线。英文：Subsequence。
Q3：核心思路 —— 为什么贪心就够？ —— 怎么理解？
A：像按清单打卡，时间线从头扫，每匹配一个就打勾，越早匹配留给后面空间越大，不回头。英文：Two-pointer Greedy。
Q4：代码实现 —— 两指针怎么动？ —— 怎么理解？
A：像两人并排走：i 指 s、j 指 t，相等则 i、j 同进，否则只 j 进；最后看 i 是否走完 s。英文：Pointer Advance。
Q5：复杂度与实战 —— 多问几个怎么办？ —— 怎么理解？
A：像排班：时间 O(n)、空间 O(1)。若有一堆 s，可预处理 t 记录每个字符下一位置做二分。英文：Preprocessing。
Q6：核心速记主线有哪些？
-
子序列不连续但保序；双指针 i、j 各走各的
-
匹配时 i、j 同进，否则只 j 进；返回 i==len(s)
-
空串是任何串的子序列
-
多个 s 时预处理 t 的下一位置，二分优化
-
最长公共子序列则是二维 DP，不贪心
口诀
A：子序列里序为先，
双针贪心不回头；
时间一遍常量占，
勾完清单即过关。