猜字谜

难度: Hard

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。

字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：

单词 word 中包含谜面 puzzle 的第一个字母。
单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）都不能作为谜底。

返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

示例：

输入：
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'。

提示：

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] 都是小写英文字母。
每个 puzzles[i] 所包含的字符都不重复。

Submission

运行时间: 455 ms

内存: 38.0 MB

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        word_int_map = {}
        for word in words:
            rep = 0
            for ch in word:
                offset = ord(ch) - ord('a')
                ind = 1 << offset
                rep = rep | ind
            word_int_map[rep] = word_int_map.get(rep, 0) + 1
        #
        def get_reps(puzzle):
            ch = puzzle[0]
            offset = ord(ch) - ord('a')
            b_rep = 1 << offset
            reps = [b_rep]
            #
            for i in range(1, len(puzzle)):
                ch = puzzle[i]
                offset = ord(ch) - ord('a')
                bias = 1 << offset
                #
                new_reps = []
                for rep in reps:
                    new_reps.append(rep)
                    new_reps.append(rep | bias)
                reps = new_reps
            return reps
        answers = [0 for puz in puzzles]
        for idx, puzzle in enumerate(puzzles):
            reps = get_reps(puzzle)
            for rep in reps:
                answers[idx] += word_int_map.get(rep, 0)
        return answers

Explain

本题解采用位运算和哈希表的方法来减少搜索空间和提高效率。首先，将每个单词转换成一个整数表示，这个整数的二进制形式中，每一位代表一个字母是否出现在单词中。然后，使用哈希表统计每个整数表示出现的次数。对于每个谜题，首先保证谜题的第一个字母在单词中出现，然后生成谜题可能的所有子集表示，并查询这些子集在之前统计的哈希表中的出现次数，将它们累加得到结果。

时间复杂度: O(W * L + P * 64)

空间复杂度: O(W + P)

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        # 创建哈希表用于记录每个单词的位掩码出现次数
        word_int_map = {}
        for word in words:
            rep = 0
            for ch in word:
                offset = ord(ch) - ord('a')
                ind = 1 << offset
                rep = rep | ind
            word_int_map[rep] = word_int_map.get(rep, 0) + 1
        # 生成谜题的所有有效子集表示
        def get_reps(puzzle):
            ch = puzzle[0]
            offset = ord(ch) - ord('a')
            b_rep = 1 << offset
            reps = [b_rep]
            for i in range(1, len(puzzle)):
                ch = puzzle[i]
                offset = ord(ch) - ord('a')
                bias = 1 << offset
                new_reps = []
                for rep in reps:
                    new_reps.append(rep)
                    new_reps.append(rep | bias)
                reps = new_reps
            return reps
        # 计算每个谜题的解的数量
        answers = [0 for puz in puzzles]
        for idx, puzzle in enumerate(puzzles):
            reps = get_reps(puzzle)
            for rep in reps:
                answers[idx] += word_int_map.get(rep, 0)
        return answers

Explore

位运算在处理这类问题时具有高效的特点，因为它能够通过整数的位表示来快速地检查字母是否存在，以及进行字母集合的并集和交集操作。每个单词或谜题的字母集合可以被转换成一个整数，其中每个位代表一个字母是否出现（例如，第0位代表'a'，第1位代表'b'等）。这种表示方式不仅节省空间，而且利用位运算（如按位与、或和异或）可以高效地实现查询和比对操作，这对于解决涉及大量数据和需要快速响应的算法问题特别有用。

确保位运算不会发生整数溢出的一个关键是选择合适的数据类型来存储位表示。在处理只有26个英文字母的情况时，可以使用32位整数（int类型）来存储，因为32位足以表示每个字母是否存在。如果字母种类超过32种，可以选择更大的数据类型，如64位的整数（long类型），甚至可以使用位向量或其他数据结构来管理更多的位。在某些编程语言中，也可以使用库函数来处理大整数或位数组，确保即使在字母种类非常多的情况下也不会溢出。

在生成谜题的所有有效子集表示时从1开始，主要是为了确保谜题的第一个字母始终出现在子集中，这是题目的一个要求。从1开始，即设置第一个字母对应的位为1，确保所有生成的子集都至少包含这个字母。这样做的优势在于直接满足了题目对于谜题解答的要求，即每个有效单词必须包含谜题的第一个字母，从而避免了生成无效的子集，提高了算法的效率和准确性。

哈希表用于统计每个整数表示（即每个字母集合）的出现次数。然而，如果单词数量极大或单词中的字母集合非常分散（即很多单词有独特的字母组合），哈希表中的条目将会非常多，这可能导致内存使用增加。此外，如果哈希函数设计不良，或者遇到大量哈希冲突，也会降低哈希表的查找和插入效率。在极端情况下，这些因素都可能导致算法效率低下。