判断子序列

下面把长串 t 画成一排格子,看 j 从左往右扫每一格;清单 s 放在公式里,i 指着「下一个要找的字符」。盯住 i 怎么一个个被点亮。

起步 · j=0 i=0：j 落在 t 的第 0 格 'a'。当前清单要找的是 s[0]='a'。问:t[0] 和 'a' 相等吗?

t[0]='a' == s[0]='a' · 命中!：相等!'a' 找到了,这一格染绿。清单指针 i 往后挪到 1,接下来要找 'b'。

j 前进 → 1：不管命不命中,j 每轮都往右走一格,现在到第 1 格 'h'。当前要找的已经变成 'b'。

t[1]='h' != s[1]='b' · 跳过：'h' 不是 'b',跳过这格。i 原地不动(还在等 'b'),只让 j 继续往右扫。

j 前进 → 2：j 走到第 2 格 'b'。还在找 'b',看看这一格对不对得上。

t[2]='b' == s[1]='b' · 命中!：相等!'b' 找到了,第 2 格染绿。i 挪到 2,最后只剩 'c' 要找了。

j 前进 → 3：j 走到第 3 格 'g'。清单只剩最后一个 'c' 没找到。

t[3]='g' != s[2]='c' · 跳过：'g' 不是 'c',跳过。i 继续等着 'c',j 往右。

j 前进 → 4：j 到第 4 格 'd'。还在找 'c'。

t[4]='d' != s[2]='c' · 跳过：'d' 也不是 'c',跳过。沉住气,'c' 也许就在后面。

j 前进 → 5：j 到最后一格第 5 格 'c'。这是 t 的末尾了,要找的也是 'c'——能对上吗?

t[5]='c' == s[2]='c' · 命中!：相等!'c' 找到了,第 5 格染绿。i 走到 3,正好等于 s 的长度——清单全找齐了!

i == len(s) · 子序列成立：i 走完了整个 s,说明 'a'→'b'→'c' 都按顺序在 t 里找到了(绿格 0→2→5,灰格是被跳过的)。返回 true。

这就是双指针匹配的魔法:遇到能匹配的就立刻匹配、绝不犹豫。早一点匹配只会让后面更宽松,所以一遍扫过去就够,不用回头。

反例预热 · s="axc"：换一个会失败的清单 s="axc" 走一遍,看看找不齐时会怎样。j 从头扫 t,先找 'a'。

t[0]='a' == 'a' · 命中：'a' 照样在第 0 格找到,i 挪到 1。可是 t 里根本没有 'x' 这个字符……

j 一路扫 · 都不是 'x'：j 一格格往后扫,'h'、'b'、'g'……没有一个是 'x',i 死死卡在 1 不动。后面还有 'd'、'c',也都不是 'x'。

扫完 t · 'x' 始终没出现：j 把 t 从头扫到尾,'x' 一次都没出现,i 永远停在 1。扫完后 i != len(s),说明 s 没找齐,返回 false。

雷区实演 · s="ba" t="ab"：s="ba" 的字符 'b'、'a' 在 t="ab" 里都出现了。但子序列讲顺序:要先找 'b' 再找 'a'。j 从第 0 格 'a' 开始。

t[0]='a' != 'b' · 跳过：第 0 格是 'a',不是要找的 'b',跳过。

t[1]='b' == 'b' · 命中,i→1：'b' 在第 1 格命中,i 挪到 1 去找 'a'。可 'a' 必须在 'b' 后面找,而 t 已经到末尾了。

扫完 t · 'a' 没机会了 → false：j 扫完 t,'a' 始终没在 'b' 之后出现,i 卡在 1。返回 false——这就是「只看字符出现、不看顺序」会出错的原因。

边界三连：先想空 s(必 true)、空 t(s 非空必 false)、字符缺失(false)三种边界,代码就稳了。

面试追问：把「贪心为何对」「多查询优化」「与 LCS 的关系」讲清楚,是这题面试的加分点。