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

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

题目描述

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

image-20260928224826918

题意分析

对 words 中的每个单词，判断能否从源串 s 中按原顺序选出字符组成它，选中的位置不要求连续，但不能重复使用。返回匹配成功的列表项数，重复单词也要分别计数。源串固定，可以把它的位置信息预处理一次，供所有单词复用。

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

核心思路

[!blue]

从左向右扫描 s，将每个字母的出现下标加入 pos[字母]，得到 26 个自然递增的位置列表。匹配单词时，pre 表示上一个字符已经使用的源串下标；当前字符只能从它自己的位置列表中，选择严格大于 pre 的位置。

每次都选择其中最早的位置。这个选择不会破坏后续匹配：如果某个解把当前字符放在更晚的位置，把它换成更早的相同字符后，剩余字符仍可使用原来的位置。因此最早匹配始终为后缀保留最多空间；若连它之后都找不到所需字符，其他更晚的选择也不可能成功。

递增列表上的 upperBound(list, pre) 返回第一个大于 pre 的元素下标。二分区间为 [left, right)：中间值小于等于 pre 时，连同左半段一起排除；中间值更大时，第一个合法位置不会在 mid 右侧，因此令 right=mid。循环结束返回的位置若等于列表长度，就表示没有可用下标。

解题步骤

  • 预处理 pos，每个源串位置只加入所属字母的列表一次。
  • 每个单词独立初始化 pre=-1，允许首字符使用源串下标 0。
  • 依次取单词字符，用二分寻找其位置列表中第一个大于 pre 的下标；不存在就立即判定该单词失败。
  • 找到后更新 pre 为实际源串位置，继续匹配下一个字符；全部匹配完成才把答案加一。

某字符在源串中不存在时，位置列表为空，二分直接返回 0，与列表长度相等，统一判为失败。不同单词不会消耗共享索引中的位置，因此每个列表项都可以独立查询，重复项也会被正确计数。

代码实现

class Solution {
    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 {
    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(\lvert s\rvert+L\log(\lvert s\rvert+1))$，L 为全部候选字符总数。
  • 空间复杂度：$O(\lvert s\rvert+26)$，每个源下标只存一次。

关键点总结

[!green]

  • 必须严格向后，不能复用同一位置。
  • 列表长度是未找到的标记，不是合法下标。

易错点总结

[!yellow]

  • 前值从零开始，会排除源串首字符。
  • 查大于等于前值，会重复使用同一字符。
  • 先去重单词，会少计合法的重复项。

相似题目

题目 难度 关联与区别
392. 判断子序列 简单 单词是否为子序列是基础，本题批量处理很多单词，可以共享对长串的扫描或预处理。
524. 通过删除字母匹配到字典里最长单词 中等 同样批量匹配字典词，本题计数，原题按长度与字典序选择一个最优词。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/20717607
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！