猜字谜
题目描述
1178. 猜字谜 难度：困难-中等
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：
- 单词 word 中包含谜面 puzzle 的第一个字母。
- 单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
例如，如果字谜的谜面是 “abcdefg”，那么可以作为谜底的单词有 “faced”, “cabbage”, 和 “baggage”；而 “beefed”（不含字母 “a”）以及 “based”（其中的 “s” 没有出现在谜面中）都不能作为谜底。
返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。
示例：
输入：
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] 所包含的字符都不重复。
题解
初步解法
鉴于words数组、puzzles数组的长度分别为10^5、10^4，且每个字符串还有自身的长度，因此暴力解法肯定会超时。
最近在学Java HashSet的实现原理，为了保证不可重复性，并且避免待添加元素与已添加元素的一个个比较，Java采用了哈希函数。其实本题可以借鉴其思想，避免一个个查找。
那么如何设计哈希映射呢，我们注意到，words数组、puzzles数组都是小写英文字母，小写英文字母总共只有26个，那么何不用26位二进制位串表示每个单词？一旦这样表示，我们可以将二进制位串作为HashMap的key。
暴力解法是对每个puzzle字符串，按照规则比较words中每一个字符串以考察其是否符合条件。以上我们将二进制位串作为HashMap的key，但是，如何利用key查找呢？我们转化一下思路，原本我们是看每一个key是否满足条件，现在，我们穷举每个puzzle字符串满足条件的子串，再考察其是否在HashMap的key中，如此我们巧妙地利用了构造的HashMap。(为什么这么想？puzzles的每个字符串长度固定，只有7位，所有满足条件的子串只有64个，求其子串的复杂度可以忽略。)
现在还有一个问题待解决，如何求子串？对于每个puzzle字符串，除去首字母必须出现外，其余6个字母出现与否可以由6位二进制位决定，某一位为1代表字符串的某位出现，其组合共有64种。
代码：
1 class Solution { 2 public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) { 3 HashMap<Integer,Integer> map = new HashMap<>(); 4 for(int i=0;i<words.length;i++){//遍历word数组，将word数组压缩归类，HashMap键为26位压缩二进制数，值为出现的次数。 5 int key = 0; 6 for(int j=0;j<words[i].length();j++){ 7 key |= 1 << (\'z\'-words[i].charAt(j));//a对应1<<25 z对应1<<0 8 } 9 if(Integer.bitCount(key)<=7){ 10 map.put(key,map.getOrDefault(key,0)+1); 11 } 12 } 13 List<Integer> ans = new ArrayList(puzzles.length); 14 for(int i=0;i<puzzles.length;i++){//遍历谜面数组，给出解 15 int bitAdd = 0;//6位位串，决定6个字符出现与否，bitAdd高位对应puzzle字符串的低地址字符。 16 int ansI = 0; 17 for(;bitAdd<64;bitAdd++){//64种可能 18 int key = 1 << (\'z\'-puzzles[i].charAt(0));//首字母必须出现 19 for(int j=1,k=6;j<=32;j=j<<1,k--){ 20 key |= (j&bitAdd)==0?0:(1 << (\'z\'-puzzles[i].charAt(k)));//取bitAdd的某一位，如果是0，不加（加0），如果是1，或上对应位。 21 } 22 ansI += map.getOrDefault(key,0); 23 } 24 ans.add(ansI); 25 } 26 return ans; 27 } 28 }
初步解法的稍加改进
除了上面的求二进制子集的方法外，还有另外一种方法，先给出整个26位位串，直接求其26位的子集（当然，由于至多只有6位不为0 [不包括首字母，因为首字母必须出现] ，复杂度并没有增加，反而减少，因其避免了子集的每个元素一位一位的形成过程。）。方法二比方法一减少复杂度的部分就在于方法一64个子集元素的每一位要通过循环生成，而方法二是先给出64个子集元素的第一个的所有位，然后依次求另外的子集元素。
1 class Solution { 2 public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) { 3 HashMap<Integer,Integer> map = new HashMap<>(); 4 for(int i=0;i<words.length;i++){//遍历word数组，将word数组压缩归类，HashMap键为26位压缩二进制数，值为出现的次数。 5 int key = 0; 6 for(int j=0;j<words[i].length();j++){ 7 key |= 1 << (\'z\'-words[i].charAt(j)); 8 } 9 if(Integer.bitCount(key)<=7){ 10 map.put(key,map.getOrDefault(key,0)+1); 11 } 12 } 13 List<Integer> ans = new ArrayList(puzzles.length); 14 for(int i=0;i<puzzles.length;i++){//遍历谜面数组，给出解 15 int ansI = 0; 16 int mask = 0; 17 for(int j=1;j<puzzles[i].length();j++){//求出除首字母的26位二进制位串 18 mask |= 1 << (\'z\'-puzzles[i].charAt(j)); 19 } 20 int sub = mask;//包括本身 21 do{ 22 ansI += map.getOrDefault( sub|(1 << (\'z\'-puzzles[i].charAt(0))) ,0);//sub是不包括首字母的那一位的子位串，由于首字母必须存在，因此每个sub都要或上首字母的那一位 23 sub = (sub - 1)&mask; 24 }while(sub!=mask);//包括0 25 ans.add(ansI); 26 } 27 return ans; 28 } 29 }
看完题解后的另解
总结
本题中，我们学会了一种利用二进制状态压缩构造的哈希映射方法、求二进制位串子集的两种解法，另解中复习了字典树和回溯法。
这道题之所以是Hard，是因为考察的都是违反人性”直觉”的东西：
- 状态压缩：对一个单词出现过哪些字母，不能采用我们直观中的 map/set 进行记录，而要利用一个长度为 26 的二进制数来记录，对于某个字母需要计算在二进制数中的哪一位，如果出现过用 1 表示，没出现过用 0 表示
- 正难则反：不能从 words 数组出发，去检查有哪些 word 符合要求；而要反过来从 puzzle 出发，去枚举当前 puzzle 所有合法的 word，再去确定这些合法的 word 在真实的 words 数组中出现了多少次。
大家要尽量去理解这种思路的合理性，当这种思路也形成意识的时候，这种题也就不难了。