如何实现高效WordFinder类，查询可由给定字符子集组成的单词

核心思路 #

利用预处理阶段提前完成所有可预计算的操作，在查询阶段先通过轻量的规则过滤掉绝大多数不符合要求的单词，仅对少量候选单词做最终的计数校验，大幅降低每次find调用的时间开销。

预处理阶段操作 #

我们在初始化时完成以下预计算：

• 按单词长度分组：所有长度为k的单词归为同一组，查询时直接跳过长度大于输入字符列表长度的所有单词
• 预计算每个单词的字符存在性标识：字符范围有限的场景（比如小写英文字母）可以用整数位掩码，其他场景可以用frozenset，查询时快速判断单词是否包含输入字符列表外的字符
• 预存储每个单词的字符计数：优先选择固定长度数组代替Counter，减少查询时的哈希表操作开销

Python优化实现代码 #

from typing import Set, Sequence, List
import collections

class WordFinder:
    def __init__(self, words: Set[str]):
        # 结构：key=单词长度，value=列表，每个元素为(字符计数元组, 存在性标识, 单词)
        self.len_group = collections.defaultdict(list)
        self.max_word_len = 0
        # 假设所有字符都是小写英文字母，可根据业务场景调整：如果包含其他字符，可将掩码替换为frozenset(word)，用issubset做存在性校验
        for word in words:
            word_len = len(word)
            self.max_word_len = max(self.max_word_len, word_len)
            # 计算字符计数元组
            cnt = [0] * 26
            mask = 0
            for c in word:
                idx = ord(c) - ord('a')
                cnt[idx] += 1
                mask |= 1 << idx
            self.len_group[word_len].append((tuple(cnt), mask, word))
    
    def find(self, characters: Sequence[str]) -> List[str]:
        chr_len = len(characters)
        res = []
        # 直接跳过所有长度超过输入字符长度的单词
        max_check_len = min(chr_len, self.max_word_len)
        if max_check_len == 0:
            return res
        
        # 预计算输入字符的计数和存在性标识
        chr_cnt = [0] * 26
        chr_mask = 0
        for c in characters:
            idx = ord(c) - ord('a')
            chr_cnt[idx] += 1
            chr_mask |= 1 << idx
        
        # 遍历所有符合长度要求的分组
        for check_len in range(1, max_check_len + 1):
            if check_len not in self.len_group:
                continue
            for word_cnt, word_mask, word in self.len_group[check_len]:
                # 快速过滤：单词有输入里没有的字符直接跳过
                if (word_mask & chr_mask) != word_mask:
                    continue
                # 计数校验：固定26次遍历，比Counter操作快
                valid = True
                for i in range(26):
                    if word_cnt[i] > chr_cnt[i]:
                        valid = False
                        break
                if valid:
                    res.append(word)
        return res

# 测试用例
words = {"wood", "word", "words"}
wf = WordFinder(words)
actual = wf.find(['o', 'w', 'o', 's', 'd', 'a', 'r'])
assert set(actual) == words

性能提升说明 #

• 长度过滤：如果输入字符列表长度为N，所有长度大于N的单词直接跳过，在单词长度差异大的场景下可以过滤掉90%以上的单词
• 存在性过滤：位运算/集合子集判断开销极低，可快速过滤掉包含输入外字符的单词，仅保留候选单词
• 计数校验优化：用固定长度数组代替Counter，避免哈希表操作开销，单次校验时间固定为O(26)，几乎可以忽略

如果单词量为10万级，该方案的find速度比原始实现快10~100倍不等，具体取决于输入字符的长度和字符覆盖范围。

内容的提问来源于stack exchange，提问作者Abhijit Sarkar