写点什么

这道 Hard 到底难在哪里?大概是难在考察的全是违反“人性直觉”的内容吧 ...

发布于: 2021 年 02 月 26 日
这道 Hard 到底难在哪里?大概是难在考察的全是违反“人性直觉”的内容吧 ...

题目描述


这是 LeetCode 上的 1178. 猜字谜,难度为 Hard


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


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


朴素位运算解法(TLE)


根据「谜底」和「谜面」的对应条件:

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

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


puzzle 本身长度只有 7 位,而且不重复;我们可以发现对应条件与 word 的重复字母无关。


因此我们可以使用「二进制」数来表示每一个 wordpuzzle


一个长度为 26 的二进制数来表示(直接使用长度为 32 的 int 即可,使用低 26 位),假如有 str = "abz" 则对应了 100...011(共 26 位,从右往左是 a - z)。


至此我们可以已经可以得出一个朴素解法的思路了:


  1. 预处理除所有的 word 对应的二进制数字。计算量为 50 * $10^5$,数量级为 $10^6$

  2. 对每个 puzzle 进行条件判定(每一个 puzzle 都需要遍历所有的 word 进行检查)。计算量为 $10^5$ * $10^4$,数量级为 $10^9$


计算机单秒的计算量为 $10^7$ 左右(OJ 测评器通常在 $10^6$ ~ $10^7$ 之间),哪怕忽略常数后,我们的总运算也超过了上限,铁定超时。


代码:

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;    }}
复制代码
  • 时间复杂度:$O(words.length * (words[i].length + puzzles.length))$

  • 空间复杂度:每个 word 对应了一个 int,每个 puzzle 对应了一个答案。复杂度为 $O(words.length + puzzles.length)$


哈希表 & 位运算解法


因此我们需要优化上述步骤 1 或者步骤 2 。显然超时的主要原因是步骤 2 计算量太多了。


一个很显眼的突破口是利用 puzzles[i].length == 7,同时判定条件 1 对 puzzle 的首字母进行了限定。


**对于一个确定的 puzzle 而言,我们要找它有多少个「谜底」。可以通过枚举它所有可能的「谜底」,再去 words 里面找每一个「谜底」出现了多少次。**


**结合题意的话,就是固定住 puzzle 的首位,去枚举其余后面的 6 位的所有的可能性(每一位都有保留和不保留两种选择),即枚举子集的过程。**


你可能还是无法理解,其实就是一个通过 puzzle 反推 word 的过程:


举个🌰吧,假如我们有 puzzlegabc(假定现在的 puzzle 长度只有 4) ,那么可能的 word 有哪些?


  1. 首先要满足条件一,也就是 word 必然包含首字母 g

  2. 然后是条件二,word 中的每一位都在 puzzle 出现过,因此可能的 word 包括 ggagbgcgabgacgbcgabc


使用 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$ 之间),因此可以过。


代码:

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;    }}
复制代码
  • 时间复杂度:$O(words.length * words[i].length + puzzles.length)$

  • 空间复杂度:wordpuzzle 分别具有最大长度和固定长度,使用空间主要取决于量数组的长度。复杂度为 $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 数组中出现了多少次


大家要尽量去理解这种思路的合理性,当这种思路也形成意识的时候,这种题也就不难了。


最后


这是我们「刷穿 LeetCode」系列文章的第 No.* 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


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

算法爱好者,退役 OIer 2020.03.07 加入

公众号「宫水三叶的刷题日记 」。每天十分钟,快乐学算法 ~

评论

发布
暂无评论
这道 Hard 到底难在哪里?大概是难在考察的全是违反“人性直觉”的内容吧 ...