判断子序列 图解题解
这道题到底在问什么
- s
- "abc"
- t
- "ahbgdc"
- 输出
- true
最优解：一步一步想明白
- 3下面把长串 t 画成一排格子,看 j 从左往右扫每一格;清单 s 放在公式里,i 指着「下一个要找的字符」。盯住 i 怎么一个个被点亮。
- 4要找 s[0]='a'j 落在 t 的第 0 格 'a'。当前清单要找的是 s[0]='a'。问:t[0] 和 'a' 相等吗?
- 5i 前进 → 1相等!'a' 找到了,这一格染绿。清单指针 i 往后挪到 1,接下来要找 'b'。
- 6要找 s[1]='b'不管命不命中,j 每轮都往右走一格,现在到第 1 格 'h'。当前要找的已经变成 'b'。
- 7i 不动,j 继续'h' 不是 'b',跳过这格。i 原地不动(还在等 'b'),只让 j 继续往右扫。
- 8要找 s[1]='b'j 走到第 2 格 'b'。还在找 'b',看看这一格对不对得上。
- 9i 前进 → 2相等!'b' 找到了,第 2 格染绿。i 挪到 2,最后只剩 'c' 要找了。
- 10要找 s[2]='c'j 走到第 3 格 'g'。清单只剩最后一个 'c' 没找到。
- 11i 不动,j 继续'g' 不是 'c',跳过。i 继续等着 'c',j 往右。
- 12要找 s[2]='c'j 到第 4 格 'd'。还在找 'c'。
- 13i 不动,j 继续'd' 也不是 'c',跳过。沉住气,'c' 也许就在后面。
- 14要找 s[2]='c'j 到最后一格第 5 格 'c'。这是 t 的末尾了,要找的也是 'c'——能对上吗?
- 15i 前进 → 3 = len(s)相等!'c' 找到了,第 5 格染绿。i 走到 3,正好等于 s 的长度——清单全找齐了!
- 16返回 true ✓i 走完了整个 s,说明 'a'→'b'→'c' 都按顺序在 t 里找到了(绿格 0→2→5,灰格是被跳过的)。返回 true。
- 17这就是双指针匹配的魔法:遇到能匹配的就立刻匹配、绝不犹豫。早一点匹配只会让后面更宽松,所以一遍扫过去就够,不用回头。
- 18要找 s[0]='a'换一个会失败的清单 s="axc" 走一遍,看看找不齐时会怎样。j 从头扫 t,先找 'a'。
- 19i → 1,要找 'x''a' 照样在第 0 格找到,i 挪到 1。可是 t 里根本没有 'x' 这个字符……
- 20i 卡在 1 不动j 一格格往后扫,'h'、'b'、'g'……没有一个是 'x',i 死死卡在 1 不动。后面还有 'd'、'c',也都不是 'x'。
- 21i 卡在 1 < len(s)j 把 t 从头扫到尾,'x' 一次都没出现,i 永远停在 1。扫完后 i != len(s),说明 s 没找齐,返回 false。
- 25先找 s[0]='b's="ba" 的字符 'b'、'a' 在 t="ab" 里都出现了。但子序列讲顺序:要先找 'b' 再找 'a'。j 从第 0 格 'a' 开始。
- 26i 不动第 0 格是 'a',不是要找的 'b',跳过。
- 27接下来要找 'a''b' 在第 1 格命中,i 挪到 1 去找 'a'。可 'a' 必须在 'b' 后面找,而 t 已经到末尾了。
- 28i 卡在 1 != 2j 扫完 t,'a' 始终没在 'b' 之后出现,i 卡在 1。返回 false——这就是「只看字符出现、不看顺序」会出错的原因。
⚠️ 容易写错的地方
✗ 错：比较前不判 i < n 就访问 s[i]
✓ 对：先判 i < n 再比 s[i]==ch
i 走到 len(s) 后再访问 s[i] 会越界(尤其 C++/Java)
✗ 错：返回 i == len(t) 或恒 true
✓ 对：返回 i == len(s)
成立的判据是「s 全部找齐」,看的是 i 是否走完 s,与 t 长度无关
✗ 错：用「s 的字符都在 t 里出现」判断
✓ 对：必须按顺序匹配
子序列要求顺序,如 s="ba" 在 t="ab" 里字符都有但顺序不对,应为 false
完整代码（Python / C++ / Java）
Python
class Solution:
def isSubsequence(self, s, t):
i, n = 0, len(s)
for ch in t: # j 扫遍 t 的每个字符
if i < n and s[i] == ch: # 碰到就匹配
i += 1
return i == n # i 走完 s 即成立C++
class Solution {
public:
bool isSubsequence(string s, string t) {
int i = 0, n = s.size();
for (char ch : t) {
if (i < n && s[i] == ch) i++; // 碰到就匹配
}
return i == n;
}
};Java
class Solution {
public boolean isSubsequence(String s, String t) {
int i = 0, n = s.length();
for (int j = 0; j < t.length(); j++) {
if (i < n && s.charAt(i) == t.charAt(j)) i++; // 碰到就匹配
}
return i == n;
}
}复杂度
时间复杂度
O(n)
n = t 的长度。j 把 t 从头扫一遍,每格 O(1) 比较,i 至多前进 len(s) 次 → 线性
空间复杂度
O(1)
只用了 i、n 两个指针/计数,没开额外数组 → 常数空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 判断子序列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么贪心「碰到就匹配」一定正确?+
越早匹配,留给后续字符可选的位置越多(是后者的超集),不会因早匹配而错失;反证:若某解在更靠后匹配,把它提前不会变差。
大量 s 对同一 t 查询如何优化?+
预处理 t:为每个字母存出现下标的有序列表;对每个 s 维护当前在 t 的位置,二分找下一个该字母的下标,单次 O(|s|·log n)。
和「最长公共子序列」什么关系?+
s 是 t 的子序列 ⟺ LCS(s,t)==len(s)。本题因 s 固定为目标,双指针 O(n) 比 LCS 的 O(mn) DP 更快。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 判断子序列 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。