0792. 匹配子序列的单词数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 桶分组

1. 📝 题目描述

• leetcode

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

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是 none)，而不改变其余字符的相对顺序。

• 例如， “ace” 是 “abcde” 的子序列。

---

示例 1：

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

示例 2：

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

---

提示：

• 1 <= s.length <= 5 * 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• words[i]和 s 都只由小写字母组成。

2. 🎯 s.1 - 桶分组

c

typedef struct Node {
    char* word;
    struct Node* next;
} Node;

int numMatchingSubseq(char* s, char** words, int wordsSize) {
    Node* buckets[26] = {0};
    for (int i = 0; i < wordsSize; i++) {
        int idx = words[i][0] - 'a';
        Node* node = (Node*)malloc(sizeof(Node));
        node->word = words[i];
        node->next = buckets[idx];
        buckets[idx] = node;
    }
    int res = 0;
    for (int i = 0; s[i]; i++) {
        int idx = s[i] - 'a';
        Node* cur = buckets[idx];
        buckets[idx] = NULL;
        while (cur) {
            Node* next = cur->next;
            cur->word++;
            if (*cur->word == '\0') {
                res++;
                free(cur);
            } else {
                int nIdx = cur->word[0] - 'a';
                cur->next = buckets[nIdx];
                buckets[nIdx] = cur;
            }
            cur = next;
        }
    }
    for (int i = 0; i < 26; i++) {
        Node* cur = buckets[i];
        while (cur) { Node* next = cur->next; free(cur); cur = next; }
    }
    return res;
}

js

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
var numMatchingSubseq = function (s, words) {
  const buckets = Array.from({ length: 26 }, () => [])
  for (const word of words) buckets[word.charCodeAt(0) - 97].push(word)
  let res = 0
  for (const c of s) {
    const bucket = buckets[c.charCodeAt(0) - 97]
    buckets[c.charCodeAt(0) - 97] = []
    for (const word of bucket) {
      if (word.length === 1) {
        res++
      } else {
        const rest = word.slice(1)
        buckets[rest.charCodeAt(0) - 97].push(rest)
      }
    }
  }
  return res
}

py

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        from collections import defaultdict
        buckets = defaultdict(list)
        for word in words:
            buckets[word[0]].append(iter(word[1:]))
        res = 0
        for c in s:
            bucket = buckets.pop(c, [])
            for it in bucket:
                nxt = next(it, None)
                if nxt is None:
                    res += 1
                else:
                    buckets[nxt].append(it)
        return res

• 时间复杂度：$O(n+\sum |w_i|)$，其中 n 是 s 的长度，$\sum |w_i|$ 是所有单词长度之和
• 空间复杂度：$O(m)$，其中 m 是单词数量

算法思路：

• 将所有单词按当前等待匹配的字符分入 26 个桶中
• 遍历 s，每次取出对应桶中的单词，匹配一个字符后重新入桶或计数