亲宝软件园·资讯

展开

2021.02.27 1178.猜字谜

#Hickey 人气:0

题目描述

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 数组中出现了多少次。

大家要尽量去理解这种思路的合理性,当这种思路也形成意识的时候,这种题也就不难了。

 

加载全部内容

相关教程
猜你喜欢
用户评论