1178.猜字谜

• 难度：简浑南

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

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

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

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

示例

示例1：

输入：
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] 所包含的字符都不重复。

思路

• 二进制状态压缩 + 寻找所有子集

  1. 遍历所有words数组中的字符串

     1. 遍历word字符串的所有字符

     2. 出现过的所有字符把bitset对应的bit位设置成1(总共最多26个位，因为只用26个字母嘛)

        例如：ace 对应 10101

     3. 把的bitset存入哈希表中

  2. 遍历所有puzzles数组

     1. 遍历puzzle字符串的所有字符

     2. 出现过的所有字符把bitset对应的bit位设置成1

     3. 记录头字符的在bitset中的位置

     4. 遍历bitset的子集cur，直至cur为0

        1. 如果子集cur中的头字符对应的bit位为1，则查询哈希表是否存在当前子集cur

           • 存在，则total获取哈希表关键字cur对应的值
           • 不存在，则跳过

        2. 刷新cur，获取下一个子集

           

     5. 把total存取数组res中

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
    vector<int> res;
    
    unordered_map<int,int> map;
    //遍历所有words数组中的字符串
    for(auto& str : words){
        int bitset = 0;
        //遍历word字符串的所有字符
        for(auto& c : str)
            //出现过的所有字符把bitset对应的bit位设置成1
            bitset |= 1 << (c-'a');
        //把所有的bitset存入哈希表中
        ++map[bitset];
    }
    
    //遍历所有puzzles数组
    for(auto& str : puzzles){
        int bitset = 0;
        //遍历puzzle字符串的所有字符
        for(auto& c : str)
            //出现过的所有字符把bitset对应的bit位设置成1
            bitset |= 1 << (c-'a');
        //记录头字符的在`bitset`中的位置
        int firstChar = str[0]-'a';
        int cur = bitset;
        int total = 0;
        //遍历bitset的子集cur，直至cur为0
        while(cur){
            //如果子集cur中的头字符对应的bit位为1，则查询哈希表是否存在当前子集cur
            if((cur >> firstChar) & 1){
                auto it = map.find(cur);
                //存在，则total获取哈希表关键字cur对应的值
                if(it != map.end()) total += map[cur];
            }
            //刷新cur，获取下一个子集
            cur = (cur - 1) & bitset;    
        }
        //把total存取数组res中
        res.push_back(total);
    }
    
    return res;
}