Hard

题目描述

对于给定的谜题字符串，如果一个单词满足以下两个条件，则该单词有效：

  • 单词包含谜题的第一个字母。
  • 单词中的每个字母都在谜题中。

例如，如果谜题是 “abcdefg”，那么有效的单词是 “faced”、“cabbage” 和 “baggage”，而无效的单词是 “beefed”（不包含 ‘a’）和 “based”（包含不在谜题中的 ’s’）。

返回一个数组 answer，其中 answer[i] 是给定单词列表 words 中对于谜题 puzzles[i] 有效的单词数量。

示例 1：

输入：words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
输出：[1,1,3,2,4,0]
解释：
1 个有效单词对于 "aboveyz"："aaaa" 
1 个有效单词对于 "abrodyz"："aaaa"
3 个有效单词对于 "abslute"："aaaa", "asas", "able"
2 个有效单词对于 "absoryz"："aaaa", "asas"
4 个有效单词对于 "actresz"："aaaa", "asas", "actt", "access"
没有有效单词对于 "gaswxyz"，因为列表中没有单词包含字母 'g'。

示例 2：

输入：words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
输出：[0,1,3,2,0]

约束条件：

  • 1 <= words.length <= 10^5
  • 4 <= words[i].length <= 50
  • 1 <= puzzles.length <= 10^4
  • puzzles[i].length == 7
  • words[i] 和 puzzles[i] 由小写英文字母组成
  • 每个 puzzles[i] 不包含重复字符

解题思路

这道题的关键在于利用谜题长度只有7这个特点，使用位运算来优化解法。

思路分析：

  1. 位掩码表示：由于字母只有26个，我们可以用一个整数的二进制位来表示字符串中包含哪些字母。比如包含字母’a’就设置第0位为1，包含’b’就设置第1位为1。

  2. 有效条件转换：

    • 单词必须包含谜题的首字母
    • 单词的所有字母都必须在谜题中（即单词的位掩码是谜题位掩码的子集）

  3. 优化策略：对于每个谜题，我们需要枚举所有包含首字母的子集。由于谜题长度固定为7，最多有2^6=64个这样的子集，这比直接遍历所有单词要高效得多。

  4. 算法步骤：

    • 预处理所有单词，计算每个单词的位掩码，并用哈希表统计每种位掩码的出现次数
    • 对每个谜题，枚举所有包含首字母的子集
    • 对每个子集，在哈希表中查找对应的单词数量并累加

这种方法的时间复杂度是O(|words| + |puzzles| × 2^6)，空间复杂度是O(|words|)。

代码实现

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> wordMasks;
        
        // 预处理所有单词的位掩码
        for (const string& word : words) {
            int mask = 0;
            for (char c : word) {
                mask |= 1 << (c - 'a');
            }
            wordMasks[mask]++;
        }
        
        vector<int> result;
        for (const string& puzzle : puzzles) {
            int puzzleMask = 0;
            for (char c : puzzle) {
                puzzleMask |= 1 << (c - 'a');
            }
            
            int firstLetterBit = 1 << (puzzle[0] - 'a');
            int count = 0;
            
            // 枚举所有包含首字母的子集
            int subset = puzzleMask;
            do {
                if (subset & firstLetterBit) {
                    count += wordMasks[subset];
                }
                subset = (subset - 1) & puzzleMask;
            } while (subset);
            
            result.push_back(count);
        }
        
        return result;
    }
};

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        from collections import defaultdict
        
        word_masks = defaultdict(int)
        
        # 预处理所有单词的位掩码
        for word in words:
            mask = 0
            for c in word:
                mask |= 1 << (ord(c) - ord('a'))
            word_masks[mask] += 1
        
        result = []
        for puzzle in puzzles:
            puzzle_mask = 0
            for c in puzzle:
                puzzle_mask |= 1 << (ord(c) - ord('a'))
            
            first_letter_bit = 1 << (ord(puzzle[0]) - ord('a'))
            count = 0
            
            # 枚举所有包含首字母的子集
            subset = puzzle_mask
            while True:
                if subset & first_letter_bit:
                    count += word_masks[subset]
                if subset == 0:
                    break
                subset = (subset - 1) & puzzle_mask
            
            result.append(count)
        
        return result

public class Solution {
    public IList<int> FindNumOfValidWords(string[] words, string[] puzzles) {
        var wordMasks = new Dictionary<int, int>();
        
        // 预处理所有单词的位掩码
        foreach (string word in words) {
            int mask = 0;
            foreach (char c in word) {
                mask |= 1 << (c - 'a');
            }
            wordMasks[mask] = wordMasks.GetValueOrDefault(mask, 0) + 1;
        }
        
        var result = new List<int>();
        foreach (string puzzle in puzzles) {
            int puzzleMask = 0;
            foreach (char c in puzzle) {
                puzzleMask |= 1 << (c - 'a');
            }
            
            int firstLetterBit = 1 << (puzzle[0] - 'a');
            int count = 0;
            
            // 枚举所有包含首字母的子集
            int subset = puzzleMask;
            do {
                if ((subset & firstLetterBit) != 0) {
                    count += wordMasks.GetValueOrDefault(subset, 0);
                }
                subset = (subset - 1) & puzzleMask;
            } while (subset != 0);
            
            result.Add(count);
        }
        
        return result;
    }
}

var findNumOfValidWords = function(words, puzzles) {
    const wordMasks = new Map();
    
    // 预处理所有单词的位掩码
    for (const word of words) {
        let mask = 0;
        for (const c of word) {
            mask |= 1 << (c.charCodeAt(0) - 97);
        }
        wordMasks.set(mask, (wordMasks.get(mask) || 0) + 1);
    }
    
    const result = [];
    for (const puzzle of puzzles) {
        let puzzleMask = 0;
        for (const c of puzzle) {
            puzzleMask |= 1 << (c.charCodeAt(0) - 97);
        }
        
        const firstLetterBit = 1 << (puzzle[0].charCodeAt(0) - 97);
        let count = 0;
        
        // 枚举所有包含首字母的子集
        let subset = puzzleMask;
        do {
            if (subset & firstLetterBit) {
                count += wordMasks.get(subset) || 0;
            }
            subset = (subset - 1) & puzzleMask;
        } while (subset);
        
        result.push(count);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(W + P × 2^6)W为单词总数，P为谜题数量，每个谜题最多枚举64个子集
空间复杂度O(W)用于存储单词位掩码的哈希表