1178. 猜字谜

难度困难149

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

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

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

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

示例：

1
2
3
4
5
6
7
8
9
10
11
输入：
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] 所包含的字符都不重复。

解答：

这题有两个要思考的点，第一个是怎么压缩状态，非常自然的想到二进制，英文字母一共26位，用int完全可以表示，通过这一点可以想到一个朴素的方法（TLE）:

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
class Solution {
public:

    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        //int 二进制有32位 英文字母一共26位 出现一次该位为1
        //a最小,z最大
        //如果字谜A包含了wordB,首先A&B==1，判断A中的第一个字母有没有包含在B里面 假设该字母是00010,取反是11101，(11101|B)&(00010)表示有

        
        vector<int>result(puzzles.size(),0);
        vector<int>wordmap(words.size(),0);
        vector<int>puzzlemap(puzzles.size(),0);
        int temp;
        for(int i=0;i<words.size();++i){
            for (int j=0;j<words[i].size();j++){
                temp=1<<(int)(words[i][j]-'a');
                wordmap[i]|=temp;
            }
        }
        for(int i=0;i<puzzles.size();++i){
            for (int j=0;j<puzzles[i].size();j++){
                temp=1<<(int)(puzzles[i][j]-'a');
                puzzlemap[i]|=temp;
            }
        }
        for(int i=0;i<puzzles.size();++i){
            for(int j=0;j<words.size();++j){
                int temp=1<<(int)(puzzles[i][0]-'a');
                if((~temp|wordmap[j])&temp){
                    int a=puzzlemap[i];
                    int b=wordmap[j];
                    if((a&b)==b){
                        result[i]+=1;
                    }

                }

            }
        }
        return result;
    }
};

这个方法就是先将words,puzzles都压缩成二进制串然后一对一比较，后面比较是一个O($N^2$),并且没有利用puzzles[i].length == 7这个条件，因此会TLE；（这是TLE的分析）

根据puzzles[i].length == 7，然后可以联想到优化的方法，因为长度是固定的，所以它的子集数目也是比较小的，因此可以将words做一个unorderer_map，然后对于pussles压缩之后的每一个子集进行查询即可。

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
44
45
46
47
48
49
50
51
52
class Solution {
public:

    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        //位运算
        //int 二进制有32位 英文字母一共26位 出现一次该位为1
        //a最小,z最大

        //如何枚举一个二进制数的子集：
        //也就是10101的子集是10101,10100,10001,10000,00101,00100,00001,00000;
        /*

        int sub = k;
        do {
            sub = (sub - 1) & k;
        } while(sub != k);


        */

        unordered_map<int, int> count; 
        for (string &word: words) {//注意
            int mask = 0;
            for (char ch : word)
                mask |= (1 << (ch - 'a'));
            count[mask]+=1;//如果出现了那么对应的count那么这个count应该为1
           // cout<<count[mask];
        }

        int len=puzzles.size();
        vector<int> result(len, 0);
        for(int i=0;i<len;++i){
            string&puzzle=puzzles[i];
            int k=0;
            for(char ch:puzzle){
                k|=(1<<(ch-'a'));
            }
            int sub = k;
            do {
                sub = (sub - 1) & k;
                if ((1 << (puzzle[0] - 'a')) & sub)
                    result[i] += count[sub];
            } while(sub != k);

        }

         return result;
    }



};