LeetCode 1178. 猜字谜

2023-04-13 HGNULB 约 11 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1178. 猜字谜

题意分析

给一组单词 words 和一组谜面 puzzles，对每个谜面统计有多少个单词与之「匹配」。匹配的定义有两条：单词必须包含谜面的第一个字母；并且单词中的每一个字母都必须出现在谜面里。返回每个谜面对应的单词数。

第一件要看清的事：两条规则都只关心「某个字母在不在」，与出现次数、顺序统统无关。所以单词 "aaaaa" 和 "a" 在这道题里是同一个东西——都只贡献「含字母 a」这一个信息。把字符串塌缩成字符集合是解题的第一步。

第二件事是两条规则的方向不同：第一条是「谜面首字母 ∈ 单词」，第二条是「单词字符集 ⊆ 谜面字符集」。一个是元素归属、一个是子集包含，写代码时容易把方向搞反。

关键约束在谜面：每个 puzzles[i] 的长度恰好是 7，且其中字母互不相同。7 这个数字非常小，$2^7 = 128$，$2^6 = 64$——这明确地在提示「可以枚举谜面字符集的所有子集」。而 words 长度可达 $10^5$、puzzles 长度可达 $10^4$，$10^5 \times 10^4 = 10^9$ 的两两匹配必然超时，所以必须让某一侧被预处理成可快速查询的形式。

字符集只有 26 个小写字母，恰好能塞进一个 int 的低 26 位——这是选择位掩码的直接依据。

边界：单词的不同字母数若超过 7，它不可能是任何谜面的子集（谜面只有 7 个不同字母），可以直接丢弃；某个谜面可能一个单词都匹配不上，答案为 0；同一个单词可能在 words 里出现多次，每次都要计入。

解法：位掩码 + 子集枚举

核心思路

先看暴力：对每对 (单词, 谜面) 做一次检查。即使把两边都压成 26 位掩码，检查本身是 $O(1)$ 的（(wordMask & ~puzzleMask) == 0 且 (wordMask & firstBit) != 0），总量仍是 $10^5 \times 10^4 = 10^9$ 次，超时。

瓶颈在于逐对配对。要打破它，只能让其中一边被「归并」——注意到不同的单词可能塌缩成同一个掩码（"apple" 与 "pale" 都是 {a,p,l,e}），而且真正有效的掩码种类被「不同字母数 ≤ 7」限制得很少。于是：

把 words 预处理成哈希表 count: 字符集掩码 → 具有该掩码的单词个数。

这是全解法的核心数据结构。它把「有多少单词满足某个字符集」变成一次 $O(1)$ 查询。

接下来换个方向想：与其问「哪些单词是这个谜面的子集」，不如直接枚举所有可能的答案掩码。因为单词掩码必须是谜面掩码的子集，而谜面只有 7 个不同字母，其子集只有 $2^7 = 128$ 个。再加上「必须含首字母」这条硬性约束，可以把首字母固定住，只枚举剩下 6 个字母的子集，共 $2^6 = 64$ 个，然后每个子集都或上首字母位。首字母不参与枚举还保证了一个候选掩码只生成一次；若把它也放进可选集合，再统一或回首字母，同一候选会被重复两次。

这样每个谜面只需 64 次哈希查询，总量 $10^4 \times 64 = 6.4 \times 10^5$，轻松通过。这里的思路转换值得强调：从「筛选已有数据」变成「构造所有合法的键去查表」，正是子集枚举类问题的通用套路。

子集枚举用经典的位技巧：
sub = mask;
while (true) { 处理 sub; if (sub == 0) break; sub = (sub - 1) & mask; }
它的原理是：sub - 1 把 sub 的最低位 1 变成 0、其后的 0 全变成 1，再与 mask 相与就是「按降序排列的下一个子集」。循环从全集开始、以空集结束，不重不漏地遍历全部 $2^{\lvert mask\rvert}$ 个子集。写成 while (true) 加尾部 break，是为了让空集（sub == 0）也被处理到——空集对应「单词只含首字母」这种合法情形，写成 while (sub > 0) 就会漏掉它。

不变量是：每次循环中的 cur = sub | first 都是一个「包含首字母、且是谜面字符集子集」的合法掩码，而所有这样的掩码恰好被枚举一次。 因此把它们在 count 里的计数累加，就是该谜面的答案。

最后一处优化：建表时丢弃不同字母数超过 7 的单词。它们不可能是任何 7 字母谜面的子集，留在表里只会白占空间；这一步不影响正确性，但能显著压小哈希表。

解题步骤

把每个单词压成掩码：mask |= 1 << (c - 'a')。用「或」而不是「异或」——我们要的是「出现过」而非「出现奇数次」，"aa" 必须仍然标记为含 a。

过滤并计数：if (Integer.bitCount(mask) <= 7) count.merge(mask, 1, ...)。累加而非置 1，因为重复单词要各算一次。

拆分谜面：first = 1 << (p.charAt(0) - 'a') 单独取出首字母位；mask 只累加下标 1 到 6 的字母。若把首字母也并进 mask，再对每个子集统一执行 | first，相差首字母位的两个子集会映射到同一个键并被重复计数。

枚举其余 6 个字母的子集：sub 从 mask 开始，每轮 sub = (sub - 1) & mask 得到下一个子集。因为首字母已被排除，mask 只有 6 位，循环恰好 64 次。

合并首字母后查表：cur = sub | first，total += count.getOrDefault(cur, 0)。| first 就是把「必须含首字母」这条规则强制注入每一个候选键。

循环终止放在末尾：先处理 sub，再判断 sub == 0 退出。这样空集也会被处理成 cur = first，对应「单词的字符集恰好只有首字母」，例如单词 "aaaa" 配谜面 "aboveyz"。

记录答案：res[i] = total。

以 words = ["aaaa","asas","able","ability","actt","actor","access"]、puzzles = ["aboveyz","abrodyz"] 走一遍（答案 [1, 1]）：

先建表。"aaaa" → {a}，1 位；"asas" → {a,s}，2 位；"able" → {a,b,l,e}，4 位；"ability" → {a,b,i,l,t,y}，6 位；"actt" → {a,c,t}，3 位；"actor" → {a,c,t,o,r}，5 位；"access" → {a,c,e,s}，4 位。全部不超过 7 位，各计数 1。

处理谜面 "aboveyz"：首字母 a，first = {a}；其余字母是 b,o,v,e,y,z，mask = {b,o,v,e,y,z}。枚举 mask 的 64 个子集，每个都并上 {a} 去查表。表中的七个键里，只有 {a}（来自 "aaaa"）是 {a,b,o,v,e,y,z} 的子集且含 a——枚举到 sub = 0 时 cur = {a} 命中，计数加 1。其余键都含有 s、l、c、t 之类不在谜面里的字母，任何子集都构造不出它们。所以答案是 1。

这一步正好说明「循环必须处理 sub == 0」：若写成 while (sub > 0)，{a} 这个键永远不会被枚举到，答案会错成 0。

处理谜面 "abrodyz"：first = {a}，mask = {b,r,o,d,y,z}。同样枚举 64 个子集：{a} 命中 "aaaa" 一次。其余单词的掩码含 s、l、e、c、t、i 等谜面外的字母，均不命中。答案是 1。

再看一个需要非空子集的例子：若 words 中有 "able"（掩码 {a,b,l,e}），谜面 "ablexyz" 的 first = {a}、mask = {b,l,e,x,y,z}。枚举到 sub = {b,l,e} 时，cur = {a,b,l,e} 恰好命中，计数加 1。而谜面 "bakexyz" 的首字母是 b，first = {b}、mask = {a,k,e,x,y,z}——"able" 的掩码含 l 而 l 不在谜面里，任何子集都凑不出，正确地不计入。

最后看首字母混入 mask 的后果：words = ["a"]、谜面为 "abcdefg" 时，若枚举完整 7 位掩码并仍计算 cur = sub | first，sub = {} 与 sub = {a} 都会得到 cur = {a}，同一个单词被统计两次，答案从 1 错成 2。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer, Integer> count = new HashMap<>();
        for (String w : words) {
            int mask = 0;
            for (int i = 0; i < w.length(); i++) {
                // 用「或」标记出现过，重复字母不影响集合。
                mask |= 1 << (w.charAt(i) - 'a');
            }
            // 超过 7 个不同字母的单词不可能是任何谜面的子集，直接丢弃。
            if (Integer.bitCount(mask) <= 7) {
                count.put(mask, count.getOrDefault(mask, 0) + 1);
            }
        }

        int[] res = new int[puzzles.length];
        for (int i = 0; i < puzzles.length; i++) {
            String p = puzzles[i];
            // 首字母单独拿出，不能并进 mask，否则会枚举出不含首字母的候选。
            int first = 1 << (p.charAt(0) - 'a');
            int mask = 0;
            for (int j = 1; j < p.length(); j++) {
                mask |= 1 << (p.charAt(j) - 'a');
            }

            int total = 0;
            int sub = mask;
            while (true) {
                int cur = sub | first;
                total += count.getOrDefault(cur, 0);
                // 先处理再判空，保证空集（只含首字母）也被统计。
                if (sub == 0) {
                    break;
                }
                sub = (sub - 1) & mask;
            }
            res[i] = total;
        }
        return res;
    }
}

import "math/bits"

func findNumOfValidWords(words []string, puzzles []string) []int {
	count := make(map[int]int)
	for _, w := range words {
		mask := 0
		for i := 0; i < len(w); i++ {
			// 用「或」标记出现过，重复字母不影响集合。
			mask |= 1 << (w[i] - 'a')
		}
		// 超过 7 个不同字母的单词不可能是任何谜面的子集，直接丢弃。
		if bits.OnesCount(uint(mask)) <= 7 {
			count[mask]++
		}
	}

	res := make([]int, len(puzzles))
	for i, p := range puzzles {
		// 首字母单独拿出，不能并进 mask，否则会枚举出不含首字母的候选。
		first := 1 << (p[0] - 'a')
		mask := 0
		for j := 1; j < len(p); j++ {
			mask |= 1 << (p[j] - 'a')
		}

		total := 0
		sub := mask
		for {
			cur := sub | first
			total += count[cur]
			// 先处理再判空，保证空集（只含首字母）也被统计。
			if sub == 0 {
				break
			}
			sub = (sub - 1) & mask
		}
		res[i] = total
	}
	return res
}

复杂度分析

时间复杂度：$O(L + P \cdot 2^6)$，其中 $L$ 为所有单词的总长度、$P$ 为谜面数。建表时每个字符处理一次；每个谜面固定枚举 64 个子集，每次一次哈希查询。相比 $O(W \cdot P)$ 的两两匹配（$10^9$），这里只有约 $6.4 \times 10^5$ 次查询。

空间复杂度：$O(U)$，其中 $U$ 是保留下来的不同单词掩码数，$U \le W$；返回数组 $O(P)$ 通常不计入。

关键点总结

只关心「字母有没有出现」时，先把字符串塌缩成 26 位掩码——出现次数、顺序全部丢弃，问题从字符串题变成集合题。

面对「多对多匹配」，先看能否把一侧归并成计数表：不同单词常常塌缩成同一个掩码，这一步把 $10^5$ 个单词压成远少于此的键。

思路要从「筛选已有数据」翻转成「构造所有合法的键去查表」。约束里出现 7、$2^7 = 128$ 这样的小数字，就是在提示子集枚举可行。

子集枚举模板 sub = (sub - 1) & mask 必须配合「先处理后判空」的循环结构，否则会漏掉空集这一合法子集。

硬性约束（必须含首字母）应当从枚举空间里剔除，再在构造键时强制或回去：既把枚举量从 128 降到 64，也避免同一候选被生成两次。

用「或」而非「异或」建掩码：要的是存在性不是奇偶性。

易错点总结

错误写法：把首字母也并进 mask，枚举 128 个子集后仍统一执行 cur = sub | first。用例 words = ["a"]、puzzles = ["abcdefg"]：sub = {} 和 sub = {a} 都命中 {a}，答案算成 2，而正确答案是 1。

错误写法：子集枚举写成 while (sub > 0) { ...; sub = (sub - 1) & mask; }。用例 words = ["aaaa"]、puzzles = ["aboveyz"]：空集永远不被处理，cur = {a} 查不到，答案算成 0，而正确答案是 1。

错误写法：建掩码时用 ^= 而不是 |=。用例 words = ["aaaa"]：字母 a 出现 4 次异或后归零，掩码变成 0，该单词永远匹配不上任何谜面。

错误写法：count.put(mask, 1) 而不是累加。用例 words = ["aaaa", "a"]：两个单词塌缩成同一掩码 {a}，只记 1 次，谜面 "aboveyz" 的答案会少算成 1 而不是 2。

错误写法：匹配条件写反成「谜面字符集 ⊆ 单词字符集」。用例 words = ["able"]、puzzles = ["ablexyz"]：谜面含 x,y,z 而单词没有，会被判为不匹配，正确答案是匹配。

错误写法：(sub - 1) & mask 写成 sub - 1。用例任意 mask：sub 会遍历所有小于 mask 的整数而非它的子集，枚举量从 64 暴涨且构造出大量非法键，既慢又可能误命中。

错误写法：过滤条件写成「单词长度 ≤ 7」而不是「不同字母数 ≤ 7」。用例 words = ["aaaaaaaaaa"]：长度 10 被丢弃，但它只有 1 个不同字母，本该能匹配含 a 的谜面，答案偏小。

错误写法：位移写成 1 << c 忘记减 'a'。用例任意小写字母：移位量高达 97，Java 中按 32 取模后不同字母映射到相同比特，掩码互相碰撞，结果全错。

错误写法：对每个谜面遍历全部单词逐一检查。用例 $W = 10^5$、$P = 10^4$：$10^9$ 次判断直接超时，必须把单词侧归并成计数表。

错误写法：res[i] 忘记在每个谜面开始时把 total 归零（例如把 total 声明在外层循环之外）。用例多个谜面：后一个谜面的答案会带上前面所有谜面的累计值，结果单调递增且全错。

错误写法：枚举时用 count.containsKey(cur) 判断后只加 1。用例 words = ["aaaa","a"]：命中一个键应加上该键的计数而不是 1，重复单词会被少算。

相似题目

题目	难度	考察点
318. 最大单词长度乘积	中等	同样把单词压成 26 位掩码，判定条件改为两掩码相与为 0（无公共字母）
78. 子集	中等	子集枚举的最基础形式，可对照位运算写法与回溯写法
698. 划分为k个相等的子集	中等	用掩码表示「哪些元素已被使用」，是状态压缩的入门题
847. 访问所有节点的最短路径	困难	掩码作为 BFS 状态的一部分，展示位压缩在图搜索中的用法
208. 实现 Trie (前缀树)	中等	本题字典树解法所需的基础结构
187. 重复的DNA序列	中等	同为「把字符串编码成整数后用哈希表归并计数」的思路