X

LEETCODE 1178. Number of Valid Words for Each Puzzle 解题思路分析

题目大意:

猜字谜

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

字谜的迷面 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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1178-number-of-valid-words-for-each-puzzle-解题思路分析/
Categories: leetcode
kwantong: