匹配子序列的单词数

记住「字符分桶记下标 → 每个字符二分找第一个比 cur 大的位置 → cur 往后跳」,下面每帧都在套它。

先一遍扫 s="abcde"，把每个字符出现的位置记进桶里:a 在下标 0、b 在 1、c 在 2、d 在 3、e 在 4。这张桶表建一次、所有单词共用,这正是它比每词重扫 s 省时的地方。

轮到单词 "a"。游标 cur 从 −1 开始,表示还没用掉 s 里任何位置。接下来逐个字符,在它的桶里找第一个比 cur 大的下标。

匹配 'a':在它的桶 [0] 里,第一个比 cur=-1 大的下标是 0。把 cur 跳到 0,表示用 s 第 0 位的 'a' 接上了。s 上高亮往后推进。

"a" 的每个字符都在 s 里按顺序找到了落点(0),它是 s 的子序列,答案加一,现在是 1。

轮到单词 "bb"。游标 cur 从 −1 开始,表示还没用掉 s 里任何位置。接下来逐个字符,在它的桶里找第一个比 cur 大的下标。

匹配 'b':在它的桶 [1] 里,第一个比 cur=-1 大的下标是 1。把 cur 跳到 1,表示用 s 第 1 位的 'b' 接上了。s 上高亮往后推进。

要匹配 'b',去它的桶 [1] 里找第一个比当前 cur=1 大的下标。桶里最大的也才 1，没有比 1 更靠后的了。这个字符接不上,单词 "bb" 失败。

"bb" 没能走完,不是子序列,答案保持 1。注意它失败不是因为缺字符种类,而是同一个字符在 s 里不够用、排不出递增的位置。

轮到单词 "acd"。游标 cur 从 −1 开始,表示还没用掉 s 里任何位置。接下来逐个字符,在它的桶里找第一个比 cur 大的下标。

匹配 'a':在它的桶 [0] 里,第一个比 cur=-1 大的下标是 0。把 cur 跳到 0,表示用 s 第 0 位的 'a' 接上了。s 上高亮往后推进。

匹配 'c':在它的桶 [2] 里,第一个比 cur=0 大的下标是 2。把 cur 跳到 2,表示用 s 第 2 位的 'c' 接上了。s 上高亮往后推进。

匹配 'd':在它的桶 [3] 里,第一个比 cur=2 大的下标是 3。把 cur 跳到 3,表示用 s 第 3 位的 'd' 接上了。s 上高亮往后推进。

"acd" 的每个字符都在 s 里按顺序找到了落点(0 → 2 → 3),它是 s 的子序列,答案加一,现在是 2。

轮到单词 "ace"。游标 cur 从 −1 开始,表示还没用掉 s 里任何位置。接下来逐个字符,在它的桶里找第一个比 cur 大的下标。

匹配 'a':在它的桶 [0] 里,第一个比 cur=-1 大的下标是 0。把 cur 跳到 0,表示用 s 第 0 位的 'a' 接上了。s 上高亮往后推进。

匹配 'c':在它的桶 [2] 里,第一个比 cur=0 大的下标是 2。把 cur 跳到 2,表示用 s 第 2 位的 'c' 接上了。s 上高亮往后推进。

匹配 'e':在它的桶 [4] 里,第一个比 cur=2 大的下标是 4。把 cur 跳到 4,表示用 s 第 4 位的 'e' 接上了。s 上高亮往后推进。

"ace" 的每个字符都在 s 里按顺序找到了落点(0 → 2 → 4),它是 s 的子序列,答案加一,现在是 3。

四个单词判完:a、acd、ace 是子序列,bb 不是,共 3 个。回头看,我们只建了一次位置桶,每个单词靠「在桶里二分找第一个比 cur 大的下标」一路往后跳,没有为每个词重新扫一遍 s。

边界:空 s 时非空单词全失败(空单词仍是任何串的子序列、计入)、同一字符在 s 里不够用就失败(bb 即此)。

两个高频追问:words 极多可用「按 s 推进」的桶解到 O(|s|+Σ|w|);本题是 LC392 的多查询升级版。