LeetCode 792. 匹配子序列的单词数

约 9 分钟
文章信息 7 个分类 7 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动 腾讯
标签
数组 字符串 哈希表 动态规划 排序 二分查找 字典树
目录

题目描述

✅ 792. 匹配子序列的单词数

题意分析

给一个长字符串 s 和一个单词列表 words，统计其中有多少个单词是 s 的子序列。

子序列的含义是：从 s 里删掉任意多个字符（可以一个都不删）、保持剩下字符的相对顺序后能得到该单词。换成可操作的说法就是，能为单词的每个字符在 s 中找到一组严格递增的下标。

规模是最强的信号：s 最长 $5 \times 10^4$，words 最多 5000 个、每个最长 50。逐词做一次线性扫描是 $2.5 \times 10^8$ 次字符比较，正好卡在超时边缘。而 s 只有一份却要被反复扫描，这几乎是在明说「该预处理 s」。

边界上要留意两点：words 里可能出现重复单词，重复的要各计一次而不是去重；单词可能比 s 还长，这类必然不是子序列，匹配过程自然会失败，不需要特判。

解法：字符位置索引 + 二分查找

核心思路

暴力做法是对每个单词用双指针扫一遍 s：两个指针各自前进，单词指针走完就算成功。单次 $O( s )$，总计 $O( words \cdot s )$。

瓶颈在于 s 被从头到尾扫了 5000 遍，而且每一遍里绝大多数比较都是空转 —— 当前要找的是 'z'，指针却不得不逐个跳过成百上千个别的字母。

观察这个空转动作的本质：它要回答的问题永远是「在 s 中，下标严格大于 pre 且字符为 ch 的最小位置在哪」。既然 s 固定不变，就可以一次性把 26 个字母各自出现过的下标按升序收进 26 个列表；此后这个问题变成「在一个升序数组里找第一个大于 pre 的元素」，用二分就能 $O(\log s )$ 解决，与 s 中无关字符的数量彻底脱钩。

匹配过程要维持的不变量是：pre 恒等于「单词已匹配的那段前缀在 s 中占用的最后一个下标」，初值 -1 表示还没占用任何位置。每一步都取「大于 pre 的最小可行下标」，这是一个贪心选择 —— 尽早匹配能给后续字符留下最长的剩余空间，如果连这样都失败，那么任何其他匹配方案也一定失败。

解题步骤

  • 建 26 个列表 pos，遍历 s 一遍，把每个下标追加到对应字母的列表里。因为是顺序遍历，每个列表天然升序，无需再排序，这是后面能二分的前提。
  • 对每个单词独立调用一次判定函数，累计返回真的个数。单词之间互不影响，pos 只读不改，所以可以放心复用。
  • 判定函数里 pre 从 -1 起步，逐个处理单词的字符。用 -1 而不是 0，是因为条件是「严格大于 pre」，取 0 会把 s 的首字符排除在外。
  • 对当前字符 ch，在 pos[ch] 上二分找第一个严格大于 pre 的元素下标 idx。这是标准的上界查找：list.get(mid) <= pre 时 left = mid + 1，否则 right = mid，循环结束时 left 就是答案位置。
  • 若 idx == list.size()，说明 pos[ch] 里所有位置都被 pre 挡住（或这个字母在 s 中根本没出现），直接返回假。这一步的判断不能省，否则紧接着的取值会下标越界。
  • 否则把 pre 更新成 list.get(idx)，继续下一个字符。单词的所有字符都处理完还没失败，就返回真。

以 s = "abcde"、words = ["a", "bb", "acd", "ace"] 走一遍：

预处理后 pos['a'] = [0]、pos['b'] = [1]、pos['c'] = [2]、pos['d'] = [3]、pos['e'] = [4]，其余字母的列表为空。

"a"：pre = -1，在 [0] 里找第一个大于 -1 的元素，得下标 0、值 0，pre 更新为 0。字符用完，返回真，计数变 1。

"bb"：首个 'b'，在 [1] 里找第一个大于 -1 的元素，得值 1，pre = 1。第二个 'b'，在 [1] 里找第一个大于 1 的元素，二分停在下标 1，等于列表长度，返回假。计数不变。

"acd"：'a' 得 0，pre = 0；'c' 在 [2] 里找大于 0 的，得 2，pre = 2；'d' 在 [3] 里找大于 2 的，得 3。返回真，计数变 2。

"ace"：'a' 得 0；'c' 得 2；'e' 在 [4] 里找大于 2 的，得 4。返回真，计数变 3。

最终返回 3。注意 "bb" 的失败正是靠「严格大于」拦住的：如果条件写成「大于等于」，第二个 'b' 会再次匹配到下标 1，得出错误的真。

代码实现

class Solution {
    // 直接对每个单词逐字符扫描 s 会重复遍历同一原串，复杂度会偏高。
    public int numMatchingSubseq(String s, String[] words) {
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; i++) {
            pos[i] = new ArrayList<>();
        }

        for (int i = 0; i < s.length(); i++) {
            pos[s.charAt(i) - 'a'].add(i);
        }

        int answer = 0;
        for (String word : words) {
            if (isSubsequence(word, pos)) {
                answer++;
            }
        }

        return answer;
    }

    private boolean isSubsequence(String word, List<Integer>[] pos) {
        int pre = -1;
        for (int i = 0; i < word.length(); i++) {
            List<Integer> list = pos[word.charAt(i) - 'a'];
            int idx = upperBound(list, pre);
            if (idx == list.size()) {
                return false;
            }
            pre = list.get(idx);
        }

        return true;
    }

    private int upperBound(List<Integer> list, int target) {
        int left = 0;
        int right = list.size();

        while (left < right) {
            int mid = (left + right) >>> 1;
            if (list.get(mid) <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

func numMatchingSubseq(s string, words []string) int {
    // 直接对每个单词逐字符扫描 s 会重复遍历同一原串，复杂度会偏高。
    pos := make([][]int, 26)
    for i := 0; i < len(s); i++ {
        pos[s[i]-'a'] = append(pos[s[i]-'a'], i)
    }

    answer := 0
    for _, w := range words {
        if isSubsequence(w, pos) {
            answer++
        }
    }
    return answer
}

func isSubsequence(word string, pos [][]int) bool {
    pre := -1
    for i := 0; i < len(word); i++ {
        idx := upperBound(pos[word[i]-'a'], pre)
        if idx == len(pos[word[i]-'a']) {
            return false
        }
        pre = pos[word[i]-'a'][idx]
    }
    return true
}

func upperBound(arr []int, target int) int {
    left, right := 0, len(arr)
    for left < right {
        mid := (left + right) >> 1
        if arr[mid] <= target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

复杂度分析

  • 时间复杂度：$O( s + L \log s )$，其中 $L$ 是所有单词的字符总数。预处理扫一遍 s；此后每个单词字符只做一次二分，与 s 中无关字符的数量无关。本题量级约为 $5 \times 10^4 + 2.5 \times 10^5 \times 16$，远低于暴力的 $2.5 \times 10^8$。
  • 空间复杂度：$O( s )$，26 个列表加起来恰好装下 s 的每个下标一次，与字母表大小无关。pre 等变量都是常数级。

关键点总结

  • 「一份固定数据被反复查询」是预处理换查询速度的经典信号。看到 s 只有一个而 words 有几千个，就该想到把成本从查询侧挪到构建侧。
  • 把重复劳动抽象成一个可复用的原语，是优化的第一步。这里的原语是「找大于 pre 的最小同字符位置」，认出它之后，选二分还是选别的结构都只是实现细节。
  • 贪心地取最小可行位置之所以正确，是因为它给后续字符留下的空间最大。这类交换论证在子序列、区间调度问题里反复出现，值得单独记住。
  • 上界二分的两个细节决定成败：比较写 <= 而不是 <（对应「严格大于」），以及返回值等于长度时代表「不存在」。这两点必须成对出现。
  • 面试视角：能主动比较三种做法 —— 暴力双指针、位置索引加二分、以及按「下一个待匹配字符」给单词分桶的多指针法（$O( s + L)$）—— 并说清各自的适用场景，比只写出一种更能体现深度。
  • 面试视角：若面试官把 s 换成流式输入或允许在线追加，位置索引法依然成立（往列表末尾追加即可），而分桶法需要重构；能指出这一差异说明你考虑了数据的可变性。

易错点总结

  • 错误写法：二分找「第一个大于等于 pre」而不是「第一个严格大于 pre」。用 s = "aa"、word = "aaa" 试：每个 'a' 都重新匹配到下标 0，pre 原地不动，长度超过 s 的单词也会被判成子序列。
  • 错误写法：pre 初始化成 0。用 s = "ab"、word = "ab" 试：首字符 'a' 要找下标严格大于 0 的 a，而 a 只在下标 0，直接判假，正确答案是真。
  • 错误写法：二分返回值等于列表长度时不判断就取值。当 pos[ch] 里的下标全被 pre 挡住、或该字母在 s 中一次都没出现时，list.get(idx) 立刻下标越界。
  • 错误写法：Java 里忘记给 pos[i] 预先 new ArrayList<>()。没出现过的字母对应 null，调用 size() 直接空指针；Go 里 nil 切片的 len 是 0，靠上一条的长度判断才能兜住。
  • 错误写法：把「子序列」当成「子串」，用 s.contains(word) 判断。用 s = "abcde"、words = ["ace"] 试："ace" 不连续，会被判成 0，正确答案是 1。
  • 错误写法：先对 words 去重再统计。用 s = "a"、words = ["a", "a"] 试：题目问的是有多少个 words[i] 满足条件，答案是 2 而不是 1。
  • 错误写法：二分写成闭区间 right = list.size() - 1 却仍用 while (left < right) 配 right = mid。当答案本该是「不存在」时，left 会停在最后一个元素上而不是越过末尾，越界判断永远不触发。
  • 错误写法：为省空间只记录每个字母在 s 中最后出现的位置。用 s = "aba"、word = "ab" 试：'a' 会取到下标 2，之后再也找不到下标更大的 'b'，判假，而 "ab" 确实是子序列。

相似题目

题目 难度 考察点
115. 不同的子序列 困难 统计匹配方案数而非可行性，需二维动态规划
208. 实现 Trie (前缀树) 中等 同样以预处理换查询速度，索引的是前缀不是位置
392. 判断子序列 简单 单次判定，双指针足够；其进阶版才需位置索引
940. 不同的子序列 II 困难 统计本质不同的子序列个数，状态按末尾字符划分
1143. 最长公共子序列 中等 两串都允许删字符，求最长公共部分