## 哈希表 & 位运算解法因此我们需要优化上述步骤 1 或者步骤 2 。显然超时的主要原因是步骤 2 计算量太多了。一个很显眼的突破口是利用 `puzzles[i].length == 7`，同时判定条件 1 对 `puzzle` 的首字母进行了限定。 **对于一个确定的 `puzzle` 而言，我们要找它有多少个「谜底」。可以通过枚举它所有可能的「谜底」，再去 `words` 里面找每一个「谜底」出现了多少次。** **结合题意的话，就是固定住 `puzzle` 的首位，去枚举其余后面的 6 位的所有的可能性（每一位都有保留和不保留两种选择），即枚举子集的过程。** 你可能还是无法理解，其实就是一个通过 `puzzle` 反推 `word` 的过程：举个🌰吧，假如我们有 `puzzle` 是 `gabc`（假定现在的 `puzzle` 长度只有 4），那么可能的 `word` 有哪些？ 1. 首先要满足条件一，也就是 `word` 必然包含首字母 `g`； 2. 然后是条件二，`word` 中的每一位都在 `puzzle` 出现过，因此可能的 `word` 包括 `g`、`ga`、`gb`、`gc`、`gab`、`gac`、`gbc`、`gabc`。使用 1 和 0 代表 `puzzle` 每一位选择与否的话，其实就是对应了 1000、1100、1010、1001、1110、1101、1011、1111。搞明白了这个过程之后，我们需要对 `words` 进行词频统计，我们可以使用「哈希表」记录相同含义的 `word` 出现了多少次（相同含义的意思是包含字母类型一样的 `word`，因为答案和 `word` 的重复字符无关）这样做的复杂度/计算量是多少呢？ 1. 统计所有 `word` 的词频。计算量为 50 * 10^5，数量级为 10^6 2. 对应每个 `puzzle` 而言，由于其长度确定为 7，因此所有枚举所有可能「谜底」的数量不为2^6=64 个，可以看做是 O(1)的，检查每个可能的「谜底」在 `words` 出现次数是通过哈希表，也是近似 O(1) 的。因此在确定一个 `puzzle` 的答案时，与 `words` 的长度无关。计算量为 10^4，数量级为 10^4 计算机单秒的计算量为10^7左右（OJ 测评器通常在 10^6 ~ 10^7之间），因此可以过。代码： ```java class Solution { public List findNumOfValidWords(String[] ws, String[] ps) { // 转用「哈希表」来统计出所有的 word 所对应的二进制数值 Map map = new HashMap<>(); for (String w : ws) { int t = getBin(w); map.put(t, map.getOrDefault(t, 0) + 1); } // 判定每个 puzzle 有多少个谜底 List ans = new ArrayList<>(); for (String p : ps) ans.add(getCnt(map, p)); return ans; } int getCnt(Map 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; } } ``` * 时间复杂度：O(words.length∗words[i].length+puzzles.length) * 空间复杂度：`word` 和 `puzzle` 分别具有最大长度和固定长度，使用空间主要取决于量数组的长度。复杂度为 O(words.length+puzzles.length) ## 位运算说明 a >> b & 1 代表检查 a 的第 b 位是否为 1，有两种可能性 0 或者 1 a += 1 << b 代表将 a 的第 b 位设置为 1 (当第 b 位为 0 的时候适用) 如不想写对第 b 位为 0 的前置判断，a += 1 << b 也可以改成 a |= 1 << b *PS. 1 的二进制就是最低位为 1，其他位为 0 哦* *以上两个操作在位运算中出现频率超高，建议每位同学都加深理解。* ## 点评这道题解发到 LeetCode 之后，很多同学反映还是看不懂，还是不理解。于是我重新的思考了这道题的每一个环节。这道题之所是 Hard，是因为考察的都是违反人性”直觉”的东西： 1. 状态压缩：对一个单词出现过哪些字母，不能采用我们直观中的 map/set 进行记录，而要利用一个长度为 26 的二进制数来记录，对于某个字母需要计算在二进制数中的哪一位，如果出现过用 1 表示，没出现过用 0 表示 2. 正难则反：不能从 `words` 数组出发，去检查有哪些 `word` 符合要求；而要反过来从 `puzzle` 出发，去枚举当前 `puzzle` 所有合法的 `word`，再去确定这些合法的 `word` 在真实的 `words` 数组中出现了多少次大家要尽量去理解这种思路的合理性，当这种思路也形成意识的时候，这种题也就不难了。

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

关于作者 📝

目录

评论