题目大意：
猜字谜
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
字谜的迷面 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] 所包含的字符都不重复。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1178
解题思路分析：
这是一道难题，暴力解需要用每个谜面去和每个单词作比对，时间复杂度为10^9，这肯定会超时。我们需要换一个思路。
如题所示，判断一个谜面是否是一个单词的谜底，需要两个条件，单词中所有字母需要在谜面中出现，谜面中首字母要在单词中出现。因此我们需要先统计出每个单词中出现过哪些字母，由于都是小写字母，统计结果可以使用2进制来表现，其中a-z分别是2进制的0-25位（0是最低位）。比如字符串abd，我们可以使用1011来表示，代表了该字符串中存在a，b和d三种字母。同理，aabbccc可以使用111来表示（其实很多种字符串都可以用111来表示，比如abc，bac，cccaab等等）。我们建一个HashMap，遍历所有单词，统计每种二进制数存在的个数存入HashMap。
接下来看谜面。谜面是固定长度为7的字符串，并且谜面若是合理的谜底，它的首字符一定要存在于单词中，所以我们可以将谜面差分成2部分，首字符+剩下字符。对于每个谜面，我们需要遍历出所有的字母组合（必须包含首字母），比如：abcd，因为必须包含a，所以他应该有以下几种组合的可能，a，ab，ac，ad，abc，abd，acd和abcd，对于每种组合，我们都可以将其转化为二进制的表现形式：
a = 1; ab = 11; ac = 101; ad = 1001; abc = 111; abd = 1011; acd = 1101; abcd= 1111;
对于上面每个key，我们查看HashMap中该key存在的值，也就是所有单词列表中存在多少拥有这样字母组合的单词，说明当前谜面可以做为这些单词的谜底。累加所有key的值，就是当前谜面可以做多少单词的谜底数量。
实现代码：
public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
Map<Integer, Integer> map = new HashMap<>();
// 将每个单词转化为2进制形式
for(String word : words){
int key=0;
for(int i=0;i<word.length();i++){
// 利用位操作转化二进制数
key |= (1<<(word.charAt(i)-'a'));
}
int count = map.getOrDefault(key, 0);
map.put(key, count+1);
}
// 返回结果
List<Integer> res = new ArrayList<>();
// 循环每个谜面
for(int i=0;i<puzzles.length;i++){
// 当前谜面
String puzzle = puzzles[i];
// 将谜面首字符转为二进制作为key
int firstKey= (1<<(puzzle.charAt(0)-'a'));
// 查看map中该key的值
int count=map.getOrDefault(firstKey, 0);
// 以下操作为谜面中遍历每种字母组合
List<Integer> keyList =new ArrayList<>();
for(int j=1;j<7;j++){
List<Integer> list =new ArrayList<>();
int current = ((1<<(puzzle.charAt(j)-'a')) | firstKey);
count+=map.getOrDefault(current, 0);
list.add(current);
for(int key : keyList){
int newKey = key | current;
count+=map.getOrDefault(newKey, 0);
list.add(newKey);
}
keyList.addAll(list);
}
res.add(count);
}
return res;
}本题解法执行时间为116ms。
Runtime: 116 ms, faster than 73.80% of Java online submissions for Number of Valid Words for Each Puzzle.
Memory Usage: 57.4 MB, less than 100.00% of Java online submissions for Number of Valid Words for Each Puzzle.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1178-number-of-valid-words-for-each-puzzle-解题思路分析/