匹配子序列的单词数：桶方法 vs 二分查找

引言

问题：匹配子序列的单词数 (LC 792)

给定一个字符串 s 和一个字符串数组 words，返回 words[i] 中是 s 的子序列的单词个数。

子序列是指通过删除原字符串的某些字符（可以不删除），不改变剩余字符的相对顺序得到的新字符串。

示例：

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: "a", "acd", "ace" 是 "abcde" 的子序列

为什么面试官喜欢这道题

1. 考察优化思维：暴力解法 O(|s| × |words|) 会超时
2. 多种有效解法：桶方法 vs 二分查找 - 两者都是正确的
3. 数据结构设计：如何组织数据会影响性能
4. 实际应用场景：类似自动补全、文本匹配、DNA序列分析

---

核心思路

暴力解法对每个 word 使用双指针检查是否是 s 的子序列 - 每个 word 需要 O(|s|)。当 words 很大时，这太慢了。

关键洞察：与其独立检查每个 word，我们可以：

1. 桶方法：遍历 s 一次，同时处理所有 words
2. 二分查找：预处理 s，使每个字符的查找变为 O(log|s|)

---

交互式可视化

子序列匹配可视化

桶方法二分查找

s = "abcde", words = ["acd","ace","bb"]

步骤 1/0:

⟲ 重置← 上一步▶ 播放下一步 →0.5x1x2x4x

---

解法一：桶/队列方法

概念

把这个方法想象成事件驱动或发布-订阅系统：

算法概念	软件架构类比
26 个桶	消息队列/Topic - 每个字母一个 topic
word 放入桶	订阅消息 - word 订阅它下一个需要的字符
遍历 s	生产者发布消息 - 每个字符是一条消息
处理并移动	消费者消费 - 匹配后要么完成，要么重新订阅下一个 topic

算法步骤

1. 初始化 26 个桶（每个字母一个）
2. 将每个 word 放入其首字母对应的桶
   - 存储: (word索引, 当前匹配位置)
   
3. 对于字符串 s 中的每个字符 c:
   - 取出 bucket[c] 中的所有条目
   - 对于每个条目:
     - 位置加 1
     - 如果 位置 == word.length → word 匹配成功! count++
     - 否则 → 移动到下一个待匹配字符的桶

4. 返回 count

图解过程

s = "abcde", words = ["acd", "ace"]

初始状态:
  bucket['a'] = [{0,0}, {1,0}]   // acd@0, ace@0

处理 'a':
  - {0,0} → acd 匹配了 'a', 下一个='c' → bucket['c'] = [{0,1}]
  - {1,0} → ace 匹配了 'a', 下一个='c' → bucket['c'] = [{0,1}, {1,1}]

处理 'b':
  - bucket['b'] 为空，跳过

处理 'c':
  - {0,1} → acd 匹配了 'c', 下一个='d' → bucket['d'] = [{0,2}]
  - {1,1} → ace 匹配了 'c', 下一个='e' → bucket['e'] = [{1,2}]

处理 'd':
  - {0,2} → acd 匹配了 'd', pos=3 == len("acd") ✓ count=1

处理 'e':
  - {1,2} → ace 匹配了 'e', pos=3 == len("ace") ✓ count=2

结果: 2

代码

JavaPythonJavaScript

Loading...

复杂度分析

• 时间: $O(|s| + \sum|words[i]|)$
  • 遍历 s 一次: O(|s|)
  • 每个 word 的每个字符最多被处理一次: O(Σ|words[i]|)
• 空间: $O(|words| + \sum|words[i]|)$
  • 存储所有 words 的 (word索引, 位置) 对

---

解法二：二分查找方法

概念

预处理 s 建立位置索引，然后对每个 word，用二分查找按顺序查找字符。

s = "abcab"

位置索引:
  'a' → [0, 3]    // 'a' 出现在位置 0 和 3
  'b' → [1, 4]    // 'b' 出现在位置 1 和 4
  'c' → [2]       // 'c' 出现在位置 2

对于 word “cab”:

1. 找 ‘c’ 在位置 > -1 → 找到位置 2, lastPos = 2
2. 找 ‘a’ 在位置 > 2 → 找到位置 3, lastPos = 3
3. 找 ‘b’ 在位置 > 3 → 找到位置 4, lastPos = 4
4. 所有字符都找到 → “cab” 是子序列 ✓

二分查找：找第一个大于 Target 的位置

positions = [0, 3, 7, 12, 15]
target = 5

二分查找第一个 > 5 的值:

  [0, 3, 7, 12, 15]
   L        M     R     mid=7 > 5, 移动 R
   
  [0, 3, 7, 12, 15]
   L  M  R            mid=3 ≤ 5, 移动 L
   
  [0, 3, 7, 12, 15]
      L  R            mid=7 > 5, 移动 R
      M
      
  [0, 3, 7, 12, 15]
      R  L            L > R, 结束!
         ↑
      返回 L=2, positions[2]=7 是第一个 > 5 的值

代码

JavaPythonJavaScript

Loading...

复杂度分析

• 时间: $O(|s| + \sum(|word[i]| \times \log|s|))$
  • 预处理 s: O(|s|)
  • 对每个 word，为每个字符做二分查找: O(|word| × log|s|)
• 空间: $O(|s|)$
  • 存储 s 中所有字符的位置索引

---

方法对比

方面	桶方法	二分查找
时间复杂度	$O(\|s\| + \sum\|words[i]\|)$	$O(\|s\| + \sum(\|word[i]\| \times \log\|s\|))$
空间复杂度	$O(\|words\| + \sum\|words[i]\|)$	$O(\|s\|)$
适用场景	大量 words，单次查询	固定 s，多批次查询
预处理	无	建立位置索引
常数因子	较低	较高（有 log 因子）

何时使用哪种方法？

• 桶方法：一次性查询大量 words - 一次遍历处理完所有
• 二分查找：当 s 固定且需要多次查询不同 word 集合时

---

边界情况

1. 空字符串 s：返回 0（没有 word 可以是子序列）
2. 空 words 数组：返回 0
3. word 比 s 长：不可能是子序列
4. 字符不在 s 中：word 不可能是子序列
5. 重复的 words：分别计算每个出现

---

常见错误

1. 二分查找的边界错误：查找 > lastPos vs >= lastPos
2. 忘记清空桶：桶方法中必须处理并移除条目
3. 使用错误的比较：positions[mid] > target 不是 >=
4. 未处理空位置列表：字符可能不存在于 s 中

---

面试技巧

1. 从暴力解法开始：解释 O(|s| × |words|) 的双指针方法
2. 识别瓶颈：“我们对每个 word 重复扫描 s，做了重复工作”
3. 提出优化：批量处理（桶）或预处理（二分查找）
4. 讨论权衡：解释每种方法的适用场景
5. 编写一种解法：选择你更熟悉的那个

---

相关题目

• LC 392: 判断子序列 - 基础版本，单个 word 检查
• LC 1055: 形成字符串的最短路径 🔒 - 贪心 + 二分查找
• LC 522: 最长特殊序列 II - 子序列比较

---

总结

关键要点	详情
模式	批量处理 或 预处理 + 查询
桶方法	事件驱动，一次 s 扫描处理所有 words
二分查找	预计算位置，每个字符 O(log n) 查找
二分模板	找第一个 > target 的位置，返回 left
面试策略	两种方法都要了解，实现更擅长的那个，讨论权衡

两种解法都展示了重要的算法思维：

• 桶方法：通过并行处理避免重复工作
• 二分查找：用预处理时间换取更快的查询速度