作者：

链接：http://proprogrammar.com:443/article/844

声明：请尊重原作者的劳动，如需转载请注明出处

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] 所包含的字符都不重复。

这道难题真得有难度，我用了两种方法都超时了，看一下我的方法吧

方法1：（超时）

public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Character, Set<int[]>> map = new HashMap<>();
        List<Integer> res = new ArrayList<>();

        for(String s: words){
            int[] b = new int[27];
            int c = 0;
            for(int i = 0; i < s.length(); i++){
                if(0 == b[s.charAt(i) - 'a']){
                    b[s.charAt(i) - 'a'] = 1;
                    c++;
                }
            }
            b[26] = c;
            for(int i = 0; i < s.length(); i++){
                Set<int[]> set = map.getOrDefault(s.charAt(i), new HashSet<>());
                set.add(b);
                if(!map.containsKey(s.charAt(i))){
                    map.put(s.charAt(i), set);
                }
            }
        }

        for(String s: puzzles){
            int c = 0;
            Set<int[]> set = map.getOrDefault(s.charAt(0), new HashSet<>());
            loop:
            for(int[] arr: set){
                int len = arr[26] - 1;
                for(int i = 1; i < s.length(); i++){
                    if(arr[s.charAt(i) - 'a'] == 1){
                        len--;
                    }
                }
                if(len == 0){
                    c++;
                }
            }
            res.add(c);
        }

        return res;
    }

这个方法实在不行，每个字母对应一组单词（这组单词都含该字母），从含有puzzle首字母的那组中找符合的，三重循环，超时

方法2：（超时）

public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        boolean[][] pa = new boolean[puzzles.length][26];
        boolean[][] wa = new boolean[words.length][26];
        List<Integer>[] ws = new List[words.length];
        List<Integer> res = new ArrayList<>();

        for(int i = 0; i < puzzles.length; i++){
            String p = puzzles[i];
            for(int j = 0; j < p.length(); j++){
                if(!pa[i][p.charAt(j)-'a'])
                    pa[i][p.charAt(j)-'a'] = true;
            }
        }

        for(int i = 0; i < words.length; i++){
            String w = words[i];
            ws[i] = new ArrayList(13);
            for(int j = 0; j < w.length(); j++){
                if(!wa[i][w.charAt(j)-'a']){
                    wa[i][w.charAt(j)-'a'] = true;
                    ws[i].add(w.charAt(j)-'a');
                }
            }
        }

        for(int i = 0; i < puzzles.length; i++){
            int a = 0;
            char f = puzzles[i].charAt(0);
            loop:
            for(int j = 0; j < wa.length; j++){
                if(wa[j][f-'a']){
                    for(int k = 0; k < ws[j].size(); k++){
                        if(!pa[i][ws[j].get(k)])
                            continue loop;
                    }
                    a++;
                }
            }
            res.add(a);
        }

        return res;
    }

这里对word进行了压缩，不再用int[26]存储比较，而是用List<Integer>存储含有的那些字母，但还是三重循环，超时

看一下官方题解

官方题解

方法一：二进制状态压缩

class Solution {
    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;

            // 枚举子集方法一
            // for (int choose = 0; choose < (1 << 6); ++choose) {
            //     int mask = 0;
            //     for (int i = 0; i < 6; ++i) {
            //         if ((choose & (1 << i)) != 0) {
            //             mask |= (1 << (puzzle.charAt(i + 1) - 'a'));
            //         }
            //     }
            //     mask |= (1 << (puzzle.charAt(0) - 'a'));
            //     if (frequency.containsKey(mask)) {
            //         total += frequency.get(mask);
            //     }
            // }

            // 枚举子集方法二
            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;
    }
}

看了好久才看懂，因为puzzle无序，word无序，用int位表示有无就可以了（int32位表示26个字母够了），这里用map保存所有word中出现的字母，可能用重复（保存次数，不用重复比较），而且不大于7（大于7不行，因为puzzle只有7个字母），这里要获取puzzle的所有子集，是这句：subset = (subset - 1) & mask; 不好理解，自己写个二进制数做一下就明白了，二重循环就不超时了

方法二：字典树

class Solution {
    TrieNode root;

    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        root = new TrieNode();
        
        for (String word : words) {
            // 将 word 中的字母按照字典序排序并去重
            char[] arr = word.toCharArray();
            Arrays.sort(arr);
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < arr.length; ++i) {
                if (i == 0 || arr[i] != arr[i - 1]) {
                    sb.append(arr[i]);
                }
            }
            // 加入字典树中
            add(root, sb.toString());
        }

        List<Integer> ans = new ArrayList<Integer>();
        for (String puzzle : puzzles) {
            char required = puzzle.charAt(0);
            char[] arr = puzzle.toCharArray();
            Arrays.sort(arr);
            ans.add(find(new String(arr), required, root, 0));
        }
        return ans;
    }

    public void add(TrieNode root, String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            if (cur.child[ch - 'a'] == null) {
                cur.child[ch - 'a'] = new TrieNode();
            }
            cur = cur.child[ch - 'a'];
        }
        ++cur.frequency;
    }

    // 在回溯的过程中枚举 puzzle 的所有子集并统计答案
    // find(puzzle, required, cur, pos) 表示 puzzle 的首字母为 required, 当前搜索到字典树上的 cur 节点，并且准备枚举 puzzle 的第 pos 个字母是否选择（放入子集中）
    // find 函数的返回值即为谜底的数量
    public int find(String puzzle, char required, TrieNode cur, int pos) {
        // 搜索到空节点，不合法，返回 0
        if (cur == null) {
            return 0;
        }
        // 整个 puzzle 搜索完毕，返回谜底的数量
        if (pos == 7) {
            return cur.frequency;
        }

        // 选择第 pos 个字母
        int ret = find(puzzle, required, cur.child[puzzle.charAt(pos) - 'a'], pos + 1);

        // 当 puzzle.charAt(pos) 不为首字母时，可以不选择第 pos 个字母
        if (puzzle.charAt(pos) != required) {
            ret += find(puzzle, required, cur, pos + 1);
        }

        return ret;
    }
}

class TrieNode {
    int frequency;
    TrieNode[] child;

    public TrieNode() {
        frequency = 0;
        child = new TrieNode[26];
    }
}

这里要排序和去重，好像很费时，好在word和puzzle都很短，另外也要找puzzle所有子串，这里是用递归的方法，好在puzzle只有7个字母，所以也不会超时

总结一下：这里通过puzzle的for循环而不是word的for循环来做是因为word的数量比puzzle大10倍，所以看清题目要求很重要，很多时间也许二方面都可以做，找一个相对简单的方面来做，比如正难则反

亲爱的读者：有时间可以点赞评论一下