从“拿命换钱”的职场吐槽到算法优化：匹配子序列的单词数

刚在网上看到一个帖子，挺让人感慨的。一位自称年薪90万的程序员，税后到手约68万，每天加班到凌晨一两点，回家还要被老婆数落是“拿命换钱”。平时消费克制，衣物穿到旧，家庭开销全由妻子打理，结果年底一算账，居然只存下20万出头。

评论区很热闹，有人觉得是“凡尔赛”，有人羡慕这收入，也有人支持妻子的担忧，认为健康比金钱更重要。从我的角度看，问题的关键或许不在于挣多少，而在于是否想清楚了自己追求的目标：是要极致的物质安全感，还是更平衡的生活与健康。

说到底，赚钱是为了让日子更踏实，而不是让全家都陷入焦虑。钱重要，命更重要，家庭关系也别丢了。好了，生活感悟聊完，咱们回归技术人的本行，来看一道与此心境颇有些“异曲同工”之妙的算法题——“匹配子序列的单词数”。

核心思路：预处理索引与二分查找

先抛结论：解决这道题，关键在于不要对每个单词都傻傻地从头到尾扫描一遍主字符串 s。高效的解法是，先将 s 预处理成一张“字符位置索引表”，之后所有单词都来查这张表，速度会快很多。

题目是这样的：给你一个字符串 s 和一个字符串数组 words，你需要返回 words 中是 s 的 子序列 的单词个数。

子序列 的定义是：可以通过删除原字符串的某些字符（也可以不删除）而不改变剩余字符的相对顺序得到的新字符串。例如：

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

答案应是 3。因为 "a"， "acd"， "ace" 都是 "abcde" 的子序列，而 "bb" 不是（因为 s 中只有一个 'b'）。

思路一：直观但低效的双指针法

最直接的思路是为 words 中的每个单词 w，都用双指针法在 s 中判断一遍。

• 指针 i 遍历 s，指针 j 遍历 w。
• 当 s[i] == w[j] 时，j 前进一位。
• 无论是否匹配，i 都前进一位。
• 如果最终 j 走到了 w 的末尾，说明 w 是子序列。

Python 示例代码如下：

def is_subsequence(s: str, w: str) -> bool:
    i = j = 0
    while i < len(s) and j < len(w):
        if s[i] == w[j]:
            j += 1
        i += 1
    return j == len(w)

def numMatchingSubseq(s: str, words: list[str]) -> int:
    count = 0
    for w in words:
        if is_subsequence(s, w):
            count += 1
    return count

这种方法的问题在于，当 s 很长（例如长度 5 * 10^4），且 words 数量也很大（同样 5 * 10^4）时，时间复杂度约为 O(len(s) * len(words))，非常容易超时。

思路二：高效的预处理+二分查找法

既然 s 是固定不变的，我们可以预先处理它一次，后续每个单词的查询都基于这个预处理结果。一个经典做法是：

1. 构建索引表：记录 s 中每个字符出现的所有位置（下标），并按升序存储。
   • 例如，对于 s = “abcde”，我们得到一个字典 pos：

     {
       'a': [0],
       'b': [1],
       'c': [2],
       'd': [3],
       'e': [4]
     }

2. 判断单词时查表：
   • 初始化 prev = -1，表示上一次在 s 中匹配到的位置。
   • 遍历单词 w 的每个字符 ch。
   • 在 pos[ch] 这个有序列表中，使用二分查找寻找第一个大于 prev 的位置。
   • 如果找到了，更新 prev 为该位置，继续匹配下一个字符。
   • 如果找不到（即该字符在 prev 之后没有出现），则该单词不是子序列。

为什么用二分查找？ 因为 pos[ch] 是升序数组，我们要找的是“第一个大于 prev 的位置”，这正是二分查找的典型应用场景。

这种方法的复杂度大大降低：

• 预处理 s：O(len(s))。
• 对每个单词 w：对其每个字符进行一次二分查找，复杂度为 O(len(w) * log K)，其中 K 是字符 ch 在 s 中出现的次数。
• 总复杂度：O(len(s) + Σ(len(w) * log K))，远优于暴力方法。

Python 实现代码（附详细注释）

以下是可直接提交的 Python 代码，包含了缓存机制以应对 words 中可能存在重复单词的情况。

from collections import defaultdict
import bisect

def numMatchingSubseq(s: str, words: list[str]) -> int:
    # 1. 预处理s，构建字符位置索引表
    pos = defaultdict(list)
    for i, ch in enumerate(s):
        pos[ch].append(i)

    # 缓存，避免重复判断相同单词
    memo = {}

    def is_subsequence(w: str) -> bool:
        if w in memo:
            return memo[w]

        prev = -1  # 上一次匹配到的位置
        for ch in w:
            # 如果s中根本没有这个字符，直接失败
            if ch not in pos:
                memo[w] = False
                return False

            idx_list = pos[ch]
            # 在idx_list中二分查找第一个 > prev 的位置
            # bisect_right 返回插入点以保持有序，正好是第一个 > prev 的索引
            j = bisect.bisect_right(idx_list, prev)
            if j == len(idx_list):  # 没有找到更靠后的该字符
                memo[w] = False
                return False
            prev = idx_list[j]  # 更新匹配位置

        memo[w] = True
        return True

    ans = 0
    for w in words:
        if is_subsequence(w):
            ans += 1
    return ans

# 测试用例
print(numMatchingSubseq("abcde", ["a", "bb", "acd", "ace"]))  # 输出 3

关键细节解析

1. 缓存 memo：题目中 words 可能包含大量重复单词。使用缓存可以避免对同一个单词进行重复的判断，提升效率。
2. bisect_right 的作用：它在有序数组中寻找“大于某个值的第一个位置”。例如：

   import bisect
   a = [0, 3, 5]
   print(bisect.bisect_right(a, 0)) # 输出 1 (第一个>0的元素是a[1]=3)
   print(bisect.bisect_right(a, 5)) # 输出 3 (越界，表示没有>5的元素)

3. 空字符串处理：空串是任何字符串的子序列。上述代码中，空串 w 的 for 循环不会执行，直接返回 True，符合定义。
4. 字符不存在于 s 的情况：代码中先判断 if ch not in pos，提前返回 False，避免了不必要的二分查找，逻辑更清晰。

这道题的解法套路非常实用：当有一个固定的大字符串和大量基于它的顺序匹配查询时，预先构建字符的索引位置，再利用二分查找进行高效匹配。掌握这个思路，就能轻松解决一类类似的字符串子序列匹配问题。

在像云栈社区这样的开发者社区里，经常能看到大家分享这类将生活观察与算法思考结合起来的讨论。技术的价值，或许不仅在于解决问题本身，也在于为我们提供一种理解复杂世界的清晰逻辑。