What is the best approach to solve the "Number of Valid Words for Each Puzzle" problem?

The best approach is using bitmasking to efficiently represent both words and puzzles, combined with hash tables to count the valid word matches for each puzzle.

How can I optimize my solution for "Number of Valid Words for Each Puzzle"?

Optimize by precomputing bitmasks for all words, storing them in a hash table, and using bitwise operations to check for valid word matches for each puzzle.

What role does the 7-character length of the puzzles play in this problem?

The 7-character length is crucial for optimization, as it limits the number of possible characters in each puzzle, making bitmasking an efficient solution for comparing words.

What is the time complexity of the "Number of Valid Words for Each Puzzle" problem?

The time complexity is O(n + m), where n is the number of words and m is the number of puzzles, due to precomputing word bitmasks and efficiently checking valid words for each puzzle.

Can I use a brute-force approach for this problem?

While a brute-force approach is possible, it is inefficient. The optimal solution leverages bitmasking and hash tables to significantly reduce computational complexity.

#1178

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

猜字谜

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：单词 word 中包含谜面 puzzle 的第一个字母。单词 word 中的每一个字母都可以在谜面 puzzle 中找到…

数组哈希表字符串位运算字典树

题目描述

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

字谜的迷面 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] 所包含的字符都不重复。

lightbulb

解题思路

方法一：状态压缩 + 哈希表 + 子集枚举

根据题目描述，对于字谜数组 $puzzles$ 中的每一个字谜 $p$ ，我们需要统计有多少个单词 $w$ 包含了字谜 $p$ 的第一个字母，且 $w$ 的每一个字母都可以在 $p$ 中找到。

由于每个单词重复的字母只需要统计一次，因此，我们可以使用二进制状态压缩的方法，将每个单词 $w$ 转换成一个二进制数 $mask$ ，其中 $mask$ 的第 $i$ 位为 $1$ ，当且仅当字母 $i$ 在单词 $w$ 中出现过。我们用哈希表 $cnt$ 统计所有单词的状态压缩后的值出现的次数。

接下来，遍历字谜数组 $puzzles$ ，对于每一个字谜 $p$ ，我们注意到其长度固定为 $7$ ，因此我们只需要枚举 $p$ 的子集，如果该子集包含 $p$ 的第一个字母，那么我们查找其在哈希表中对应的值并累加到当前字谜的答案中。

遍历结束后，我们就可以得到字谜数组 $puzzles$ 中每个字谜对应的谜底数量，将其返回即可。

时间复杂度 $O(m \times |w| + n \times 2^{|p|})$ ，空间复杂度 $O(m)$ 。其中 $m$ 和 $n$ 分别为数组 $words$ 和 $puzzles$ 的长度，而 $|w|$ 和 $|p|$ 分别为数组 $words$ 中单词的最大长度和数组 $puzzles$ 中字谜的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        cnt = Counter()
        for w in words:
            mask = 0
            for c in w:
                mask |= 1 << (ord(c) - ord("a"))
            cnt[mask] += 1

        ans = []
        for p in puzzles:
            mask = 0
            for c in p:
                mask |= 1 << (ord(c) - ord("a"))
            x, i, j = 0, ord(p[0]) - ord("a"), mask
            while j:
                if j >> i & 1:
                    x += cnt[j]
                j = (j - 1) & mask
            ans.append(x)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding bitmasking and its application to problems with constraints on character sets.
question_mark
Efficient handling of large datasets, particularly when there are multiple queries for the same input.
question_mark
Effective use of hash tables and bit manipulation to avoid brute-force solutions.

warning

常见陷阱

外企场景

error
Not accounting for the first letter of each puzzle word, which is required to be part of every valid word.
error
Using brute force to check every word against every puzzle, leading to inefficient solutions.
error
Overlooking the need to optimize for the fact that puzzles are only 7 characters long, missing the opportunity for bitmask comparisons.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider handling cases with more complicated character sets or larger puzzle sizes.
arrow_right_alt
Explore how the problem might change if the number of words or puzzles grows beyond the current constraints.
arrow_right_alt
Test variations where words or puzzles contain repeated characters or longer lengths, which will impact the approach.

help

常见问题

外企场景

继续练习

#1177 构建回文串检测 #820 单词的压缩编码 #792 匹配子序列的单词数