Medium

题目描述

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

字符串的子序列是从原始字符串生成的新字符串，可以删除一些字符（也可以不删除），但不改变剩余字符的相对顺序。

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

示例 1：

输入：s = "abcde", words = ["a","bb","acd","ace"]
输出：3
解释：words 中有三个字符串是 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
  • s 和 words[i] 仅由小写英文字母组成

解题思路

这道题要求统计有多少个单词是字符串 s 的子序列。有几种常见的解法：

方法一：暴力匹配 对每个单词，使用双指针判断是否为 s 的子序列。时间复杂度较高。

方法二：字符分组优化（推荐） 核心思想是按字符对单词进行分组。为每个字符维护一个队列，存储等待匹配该字符的单词及其当前匹配位置。遍历 s 的每个字符时，处理对应队列中的所有单词：

  • 如果单词完全匹配，计数加一
  • 否则将单词移到下一个字符的队列中

这种方法避免了重复扫描，大大提高了效率。

方法三：预处理 + 二分查找 预处理 s，记录每个字符的所有出现位置。对每个单词，依次查找每个字符在当前位置之后的最小位置，使用二分查找优化。

方法二在实际应用中性能最佳，既避免了重复计算，又减少了内存开销。

代码实现

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<queue<pair<string, int>>> buckets(26);
        
        // 初始化：将所有单词放入对应的第一个字符的桶中
        for (const string& word : words) {
            buckets[word[0] - 'a'].push({word, 0});
        }
        
        int count = 0;
        for (char c : s) {
            int bucket_index = c - 'a';
            int bucket_size = buckets[bucket_index].size();
            
            // 处理当前字符对应桶中的所有单词
            for (int i = 0; i < bucket_size; i++) {
                auto [word, pos] = buckets[bucket_index].front();
                buckets[bucket_index].pop();
                
                pos++;
                if (pos == word.length()) {
                    count++;
                } else {
                    buckets[word[pos] - 'a'].push({word, pos});
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        from collections import defaultdict, deque
        
        # 按第一个字符分组
        buckets = defaultdict(deque)
        for word in words:
            buckets[word[0]].append((word, 0))
        
        count = 0
        for char in s:
            bucket = buckets[char]
            bucket_size = len(bucket)
            
            # 处理当前字符对应的所有单词
            for _ in range(bucket_size):
                word, pos = bucket.popleft()
                pos += 1
                
                if pos == len(word):
                    count += 1
                else:
                    buckets[word[pos]].append((word, pos))
        
        return count

public class Solution {
    public int NumMatchingSubseq(string s, string[] words) {
        Queue<(string word, int pos)>[] buckets = new Queue<(string, int)>[26];
        for (int i = 0; i < 26; i++) {
            buckets[i] = new Queue<(string, int)>();
        }
        
        // 初始化：将所有单词放入对应的第一个字符的桶中
        foreach (string word in words) {
            buckets[word[0] - 'a'].Enqueue((word, 0));
        }
        
        int count = 0;
        foreach (char c in s) {
            int bucketIndex = c - 'a';
            int bucketSize = buckets[bucketIndex].Count;
            
            // 处理当前字符对应桶中的所有单词
            for (int i = 0; i < bucketSize; i++) {
                (string word, int pos) = buckets[bucketIndex].Dequeue();
                pos++;
                
                if (pos == word.Length) {
                    count++;
                } else {
                    buckets[word[pos] - 'a'].Enqueue((word, pos));
                }
            }
        }
        
        return count;
    }
}

var numMatchingSubseq = function(s, words) {
    const buckets = Array.from({length: 26}, () => []);
    
    for (let word of words) {
        buckets[word.charCodeAt(0) - 97].push({word, index: 0});
    }
    
    let count = 0;
    
    for (let char of s) {
        const charCode = char.charCodeAt(0) - 97;
        const currentBucket = buckets[charCode];
        buckets[charCode] = [];
        
        for (let item of currentBucket) {
            item.index++;
            if (item.index === item.word.length) {
                count++;
            } else {
                const nextChar = item.word.charCodeAt(item.index) - 97;
                buckets[nextChar].push(item);
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(s.length + Σword.length)，每个字符只被访问一次
空间复杂度O(words.length)，存储单词及其匹配状态

相关题目