追加字符以获得子序列

记牢这一句:一个指针 j 顺着 t 走,在 s 里从左到右能对上就前进,对不上就跳过;s 扫完 j 停在哪,答案就是 t 的长度减去 j。下面每一帧都在套这句话。

先把两个串摆好。上面这一排是 s,coaching,一共 8 个字符,我们要在它里面从左到右顺序匹配。右边这一列是目标串 t,coding,共 6 个字符,谁被匹配到就打勾。现在还一个都没开始,匹配进度 j 是 0,高亮的是 t 的第一个字符 c,那是我们最先要在 s 里找的。

指针就位。i 指向 s 的第 0 个字符,也就是 c;j 指向 t 的第 0 个字符,也是 c。接下来的规则很简单,拿 s[i] 和 t[j] 比:相等就说明 t 的这个字符在 s 里对上了,j 前进;不相等就只把 s 往后挪,j 原地不动。

扫到 s 的第 0个字符 c。现在 j 是 0,要找的 t[0] 是 c。把这两个放一起比一比:c 和 c 一样吗?

一样!c 正好是要找的 t 字符,命中。把 s 的这一格标绿,j 前进到 1,下一个要在 s 里找的目标变成 t[1] 等于 o。已经顺次对上 1 个了。

扫到 s 的第 1个字符 o。现在 j 是 1,要找的 t[1] 是 o。把这两个放一起比一比:o 和 o 一样吗?

一样!o 正好是要找的 t 字符,命中。把 s 的这一格标绿,j 前进到 2,下一个要在 s 里找的目标变成 t[2] 等于 d。已经顺次对上 2 个了。

扫到 s 的第 2个字符 a。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:a 和 d 一样吗?

不一样。a 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。

扫到 s 的第 3个字符 c。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:c 和 d 一样吗?

不一样。c 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。

扫到 s 的第 4个字符 h。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:h 和 d 一样吗?

不一样。h 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。

扫到 s 的第 5个字符 i。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:i 和 d 一样吗?

不一样。i 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。

扫到 s 的第 6个字符 n。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:n 和 d 一样吗?

不一样。n 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。

扫到 s 的第 7个字符 g。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:g 和 d 一样吗?

不一样。g 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。

s 的 8 个字符全部扫完了。回头看 j,它停在 2。这说明 t 的前 2 个字符,也就是 co,已经能在 s 里按顺序找到(看那两个绿格)。可是 j 没能走到底,t 后面还剩字符没匹配上。

看看 t 里没打勾的部分:ding,一共 4 个字符。它们在 s 里已经没有机会再顺序补齐了,因为 s 已经扫到头。想让 t 成为子序列,只能把这 ding 原样接到 s 的末尾。

答案出来了。t 的长度是 6,已经顺序匹配上 2 个,还差 6 减 2 等于 4 个。这 4 就是要往 s 末尾追加的最少字符数,追加后 s 变成 coachingding,t 就成了它的子序列。

边界想清:t 本就是子序列答案 0、一个都对不上答案就是 |t|、中间对上一半就追加剩下的。

面试重点:是子序列判定的升级版、尽早匹配可用交换论证证明最优、时间 O(|s|) 空间 O(1)。