猜字谜

2021-02-26

1178. 猜字谜

难度困难141收藏分享切换为英文接收动态反馈

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

字谜的迷面 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中的每一个单词使用哈希转换成对应的二进制数字，例如一个单词是abc，生成的二进制数字为

00000000 00000000 00000000 00000111

其对应的十进制数字为7，将7作为Map的键，将单词出现的次数作为Map的值统计所有单词出现的次数。

对于puzzle中的单词同样将数字转化成二进制的数字，枚举每个puzzle的二进制数字的子集，判断子集的数字是否在Map中出现来计算谜底的数量。


class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer,Integer> wMap=new HashMap<>();

        int m=words.length;
        int n=puzzles.length;

        for(int i=0;i<m;i++){
            String w=words[i];

            int mask=0;
            for(int j=0;j<w.length();j++){
                mask|=(1<<w.charAt(j)-'a');
            }
            if(Integer.bitCount(mask)<=7){
                wMap.put(mask,wMap.getOrDefault(mask,0)+1);
            }
        }

        List<Integer> res=new ArrayList<>();
        for(int i=0;i<n;i++){
            int total=0;
            String p=puzzles[i];
            int mask=0;
            for(int j=1;j<7;j++){
                mask|=(1<<p.charAt(j)-'a');
            }
            int subset=mask;
            do{
                int s= subset|(1<<p.charAt(0)-'a');
                if(wMap.containsKey(s))total+=wMap.get(s);
                subset=(subset-1)&mask;
            }while(subset!=mask);

            res.add(total);
        }
        return res;
    }
}

哈希表+枚举二进制数子集

枚举二进制子集方法有两种如下代码所示

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;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/solution/cai-zi-mi-by-leetcode-solution-345u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

字典树

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];
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/solution/cai-zi-mi-by-leetcode-solution-345u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

字典树

class Solution {
    TrieNode root = new TrieNode();
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {

        for (String word : words) {
            char[] w = word.toCharArray();
            Arrays.sort(w);
            StringBuilder bd = new StringBuilder();
            TrieNode temp = root;
            for (int i = 0 ; i < w.length ; i++) {
                if (bd.length() == 0 || bd.charAt(bd.length() - 1) != w[i]) {
                    bd.append(w[i]);
                    temp = temp.add(w[i]);
                }
            }
            temp.count++;
        }
        List<Integer> ans = new ArrayList<>();
        for(String puzzle : puzzles) {
            char[] p = puzzle.toCharArray();
            Arrays.sort(p);
            ans.add(find(p,root,0,puzzle.charAt(0)));
        }
        return ans;
    }

    Integer find(char[] puzzle,TrieNode cur,int index,char pre) {
        if (cur == null)
            return 0;
        if (index == 7)
            return cur.count;
        int ans = find(puzzle,cur.dect[puzzle[index] - 'a'],index + 1,pre);
        if (pre != puzzle[index])
            ans += find(puzzle,cur,index + 1,pre); 
        return ans;
    }

    class TrieNode {
        TrieNode[] dect = new TrieNode[26];
        int count = 0;
        TrieNode () {   
        }
        TrieNode add(char ch) {
            if (this.dect[ch - 'a'] == null) {
                this.dect[ch - 'a'] = new TrieNode();
            }
            return this.dect[ch - 'a'];
        }
    }
}

参考文献

LeetCode-Solution

かなみ的评论