LeetCode 1178. 猜字谜

约 6 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
数组 字符串 哈希表 位运算 字典树

题目描述

✅ 1178. 猜字谜

image-20260929075300287

image-20260929075300441

题意分析

对每个谜面，统计单词列表里有多少个单词同时满足两个条件：单词的每一种字母都出现在谜面中，并且单词必须包含谜面的第一个字母。

谜面恰好包含七个不同的小写字母，单词可以重复使用其中某个字母，不要求字母次数一致，也不要求按谜面顺序排列。统计的是单词条目数量，即使多个单词的字母集合相同，也要分别计数。

解法：位掩码 + 子集枚举

核心思路

[!blue]

匹配只依赖出现过哪些字母，可以把每个单词压成二十六位集合掩码：读到字母就按位或上对应位，重复出现不会改变掩码。用哈希表统计每一种集合对应多少个单词，不保存字符顺序或重复次数。

谜面最多提供七种字母，因此单词不同字母超过七种时不可能匹配任何谜面，可以提前跳过。这里限制的是集合大小，不是单词长度；保留下来的相同掩码仍要累加频次。

对一个谜面，首字母必须选择，其他六个字母可以自由选择是否出现在单词集合中。因此固定首字母位，只枚举其余六位的所有子集，再将首位或回去，就恰好得到六十四个可能的合法单词集合。每个满足题意的集合对应其中唯一一个子集，查表求和既不会漏掉，也不会重复计数。

子集枚举从可选位全集 mask 开始，用 sub = (sub - 1) & mask 移到下一个。减一会清掉最低的一个置一位并让更低位成为可选状态，再与全集相与去掉不属于谜面的位，得到下一个更小子集；反复执行就能逐个遍历所有子集。

空子集也需要处理，它与固定首位组合后，代表只使用首字母的单词集合。处理零后必须结束，因为继续执行减一并与全集相与，会重新回到全集，导致重复循环。

解题步骤

  1. 扫描所有单词，用按位或生成字符集合掩码，统计不超过七种字母的掩码频次。
  2. 对每个谜面单独保存首字母位，用其余六个字母形成可选集合。
  3. 从可选全集开始枚举子集，将当前子集与首位合并后查频次表，累加对应单词数。
  4. 当前子集为零时结束；否则通过 (sub - 1) & mask 继续枚举。
  5. 将累计数量写入当前谜面的答案。

代码实现

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];
            // 只枚举其余六位，再固定首位；否则同一候选会被重复计数。
            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 {
        // 只枚举其余六位，再固定首位；否则同一候选会被重复计数。
        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 + 64P)$，L 为单词总字符数，P 为谜面数，每个谜面固定查询六十四个候选集合。
  • 空间复杂度：$O(U)$ 保存不同有效掩码的单词频次，U 为这些掩码的数量；返回结果另占 $O(P)$。

关键点总结

[!green]

  • 字母存在性使用 OR，不应使用表示次数奇偶的 XOR。
  • 必选首字母与可选六个字母分开，才能唯一生成所有合法候选集合。
  • 哈希表统计同集合的单词总数，不只是记录集合是否出现。
  • 空子集有实际含义，先统计它，再结束枚举。

易错点总结

[!yellow]

  • 根据单词长度大于七就丢弃，误删只有少量不同字母但含很多重复字符的单词。
  • 忽略同掩码的多个单词，会少算题目要求的单词数量。
  • 枚举首字母也可以不选，却没有强制检查首字母，会计入缺少必选字母的单词。
  • 把首字母放进可选集合后又统一或回，会让不同子集生成相同候选而重复计数。
  • 跳过零子集会漏掉只含首字母的集合，处理零之后仍继续循环又会重复枚举。

相似题目

题目 难度 关联与区别
318. 最大单词长度乘积 中等 同样把单词字符集合编码成位掩码，原题判断不相交，本题判断单词是谜面子集且含首字母。
1239. 串联字符串的最大长度 中等 同样忽略字符原顺序并按集合关系筛选，本题对固定短谜面枚举子集，原题选择互不重叠的单词集合。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/61996916
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！