写点什么

【LeetCode】猜字谜 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 02 月 26 日

题目

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


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


单词 word 中包含谜面 puzzle 的第一个字母。

单词 word 中的每一个字母都可以在谜面 puzzle 中找到。

例如,如果字谜的谜面是 "abcdefg",那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage";而 "beefed"(不含字母 "a")以及 "based"(其中的 "s" 没有出现在谜面中)都不能作为谜底。

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


代码

public class DayCode {    public static void main(String[] args) {        String[] words = new String[]{"aaaa","asas","able","ability","actt","actor","access"};        String[] puzzles = new String[]{"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};        List<Integer> ans = new DayCode().findNumOfValidWords(words, puzzles);        System.out.println("ans is " + ans.toString());    }
/** * https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/ * @param words * @param puzzles * @return */ public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) { Map<Integer, Integer> frequency = new HashMap<Integer, Integer>();
for (String word : words) { int mask = 0; for (int i = 0; i < word.length(); ++i) { char ch = word.charAt(i); mask |= (1 << (ch - 'a')); } if (Integer.bitCount(mask) <= 7) { frequency.put(mask, frequency.getOrDefault(mask, 0) + 1); } }
List<Integer> ans = new ArrayList<Integer>(); for (String puzzle : puzzles) { int total = 0; int mask = 0; for (int i = 1; i < 7; ++i) { mask |= (1 << (puzzle.charAt(i) - 'a')); } int subset = mask; do { int s = subset | (1 << (puzzle.charAt(0) - 'a')); if (frequency.containsKey(s)) { total += frequency.get(s); } subset = (subset - 1) & mask; } while (subset != mask);
ans.add(total); } return ans; }}
复制代码

总结

  • 今天的每日一题比较难,又是一个难忘的节日。这个代码和思路需要多多回味。


发布于: 2021 年 02 月 26 日阅读数: 16
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】猜字谜Java题解