LeetCode 1178. 猜字谜

Categories:

题目描述
思路分析
1. 解法一：位掩码 + 子集枚举（推荐）
相似题目

题目描述

✅ 1178. 猜字谜

思路分析

解法一：位掩码 + 子集枚举（推荐）

核心思路：

将每个单词转换为 26 位掩码，忽略包含超过 7 个不同字母的单词。

统计每个掩码出现次数。

对每个谜面：必须包含首字母，枚举其余 6 个字母的所有子集，与首字母合并后累加计数。

复杂度分析：

时间复杂度：O(W + P * 2^6)，其中 W 为单词数，P 为谜面数。

空间复杂度：O(W)，存储掩码计数。

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');
            }
            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;
    }
}

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')
        }
        if bitsCount(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
}

func bitsCount(x int) int {
    count := 0
    for x > 0 {
        x &= x - 1
        count++
    }
    return count
}

相似题目

题目	难度	考察点
318. 最大单词长度乘积	中等	位掩码
1255. 得分最高的单词集合	困难	位掩码、子集
1239. 串联字符串的最大长度	中等	位掩码
869. 重新排序得到 2 的幂	中等	位掩码
78. 子集	中等	子集枚举

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/61996916