【点评必看】这道 Hard 到底难在哪里？大概是难在考察的是违反“人性直觉”的内容吧 ...

输入：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'。

class Solution {    public List<Integer> findNumOfValidWords(String[] ws, String[] ps) {        // 预处理出所有的 word 所对应的二进制数值        List<Integer> list = new ArrayList<>();        for (String w : ws) list.add(getBin(w));        // 判定每个 puzzles 有多少个谜底        List<Integer> ans = new ArrayList<>();        for (String p : ps) ans.add(getCnt(list, p));        return ans;    }    // 判定某个 puzzles 有多少个谜底    int getCnt(List<Integer> ws, String str) {        int ans = 0;        // 获取当前 puzzles 对应的二进制数字        int t = getBin(str);        // 当前 puzzles 的首个字符在二进制数值中的位置        int first = str.charAt(0) - 'a';        for (int w : ws) {            // check 条件一：单词 word 中包含谜面 puzzle 的第一个字母            if ((w >> first & 1) == 0) continue;            // check 条件二：单词 word 中的每一个字母都可以在谜面 puzzle 中找到            if ((w & t) == w) ans++;        }        return ans;    }    // 将 str 所包含的字母用二进制标识    // 如果 str = abz 则对应的二进制为 100...011 (共 26 位，从右往左是 a - z)    int getBin(String str) {        int t = 0;        char[] cs = str.toCharArray();        for (char c : cs) {            // 每一位字符所对应二进制数字中哪一位            int u = c - 'a';            // 如果当前位置为 0，代表还没记录过，则进行记录 (不重复记录)            if ((t >> u & 1) == 0) t += 1 << u;        }        return t;    }}

class Solution {    public List<Integer> findNumOfValidWords(String[] ws, String[] ps) {        // 转用 「哈希表」来统计出所有的 word 所对应的二进制数值        Map<Integer, Integer> map = new HashMap<>();        for (String w : ws) {            int t = getBin(w);            map.put(t, map.getOrDefault(t, 0) + 1);        }        // 判定每个 puzzle 有多少个谜底        List<Integer> ans = new ArrayList<>();        for (String p : ps) ans.add(getCnt(map, p));        return ans;    }    int getCnt(Map<Integer, Integer> map, String str) {        int ans = 0;        int m = str.length();        char[] cs = str.toCharArray();        // 当前 puzzle 的首个字符在二进制数值中的位置        int first = cs[0] - 'a';        // 枚举「保留首个字母」的所有子集        // 即我们需要先固定 puzzle 的首位字母，然后枚举剩余的 6 位是否保留        // 由于是二进制，每一位共有 0 和 1 两种选择，因此共有 2^6 种可能性，也就是 2^6 = 1 << (7 - 1) = 64 种        // i 代表了所有「保留首个字母」的子集的「后六位」的二进制表示        for (int i = 0; i < (1 << (m - 1)); i++) {            // u 代表了当前可能的谜底。先将首字母提取出来            int u = 1 << first;            // 枚举「首个字母」之后的每一位            for (int j = 1; j < m; j++) {                // 如果当前位为 1，代表该位置要保留，将该位置的字母追加到谜底 u 中                if (((i >> (j - 1)) & 1) != 0) u += 1 << (cs[j] - 'a');            }            // 查询这样的字符是否出现在 `words` 中，出现了多少次            if (map.containsKey(u)) ans += map.get(u);        }        return ans;    }    // 将 str 所包含的字母用二进制标识    // 如果 str = abz 则对应的二进制为 100...011 (共 26 位，从右往左是 a - z)    int getBin(String str) {        int t = 0;        char[] cs = str.toCharArray();        for (char c : cs) {            // 每一位字符所对应二进制数字中哪一位            int u = c - 'a';            // 如果当前位置为 0，代表还没记录过，则进行记录 (不重复记录)            if ((t >> u & 1) == 0) t += 1 << u;        }        return t;    }}