【面试高频题】难度 3/5，字典树热门运用题

## 题目描述这是 LeetCode 上的 **[745. 前缀和后缀搜索](https://leetcode.cn/problems/prefix-and-suffix-search/solution/by-ac_oier-ayej/)** ，难度为 **困难**。 Tag : 「字典树」设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。实现 `WordFilter` 类： * `WordFilter(string[] words)` 使用词典中的单词 `words` 初始化对象。 * `f(string pref, string suff)` 返回词典中具有前缀 `prefix` 和后缀 `suff` 的单词的下标。如果存在不止一个满足要求的下标，返回其中最大的下标。如果不存在这样的单词，返回 $-1$ 。示例： ``` 输入 ["WordFilter", "f"] [[["apple"]], ["a", "e"]] 输出 [null, 0] 解释 WordFilter wordFilter = new WordFilter(["apple"]); wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且后缀 suff = "e" 。 ``` 提示： * $1 <= words.length <= 10^4$ * $1 <= words[i].length <= 7$ * $1 <= pref.length, suff.length <= 7$ * `words[i]`、`pref` 和 `suff` 仅由小写英文字母组成 * 最多对函数 `f` 执行 $10^4$ 次调用 ## 基本分析为了方便，我们令 `words` 为 `ss`，令 `pref` 和 `suff` 分别为 `a` 和 `b`。搜索某个前缀（后缀可看做是反方向的前缀）容易想到字典树，但单词长度数据范围只有 $7$，十分具有迷惑性，使用暴力做法最坏情况下会扫描所有的 $ss[i]$，不考虑任何的剪枝操作的话，计算量也才为 $2 \times \ 7 \times 1e4 = 1.4 \times 10^5$，按道理是完全可以过的。但不要忘记 LC 是一个具有「设定每个样例时长，同时又有总时长」这样奇怪机制的 OJ。 ## 暴力（TLE or 双百) 于是有了 `Java` 总时间超时，`TypeScripe` 双百的结果（应该是 `TypeScript` 提交不多，同时设限宽松的原因）： ![](https://upload-images.jianshu.io/upload_images/1980848-10adeea7694c9063.png) Java 代码： ```Java class WordFilter { String[] ss; public WordFilter(String[] words) { ss = words; } public int f(String a, String b) { int n = a.length(), m = b.length(); for (int k = ss.length - 1; k >= 0; k--) { String cur = ss[k]; int len = cur.length(); if (len < n || len < m) continue; boolean ok = true; for (int i = 0; i < n && ok; i++) { if (cur.charAt(i) != a.charAt(i)) ok = false; } for (int i = 0; i < m && ok; i++) { if (cur.charAt(len - 1 - i) != b.charAt(m - 1 - i)) ok = false; } if (ok) return k; } return -1; } } ``` TypeScript 代码： ```TypeScript class WordFilter { ss: string[] constructor(words: string[]) { this.ss = words } f(a: string, b: string): number { const n = a.length, m = b.length for (let k = this.ss.length - 1; k >= 0; k--) { const cur = this.ss[k] const len = cur.length if (len < n || len < m) continue let ok = true for (let i = 0; i < n && ok; i++) { if (cur[i] != a[i]) ok = false } for (let i = m - 1; i >= 0; i--) { if (cur[len - 1 - i] != b[m - 1 - i]) ok = false } if (ok) return k } return -1 } } ``` * 时间复杂度：初始化操作复杂度为 $O(1)$，检索操作复杂度为 $O(\sum_{i = 0}^{n - 1} ss[i].length)$ * 空间复杂度：$O(\sum_{i = 0}^{n - 1} ss[i].length)$ ## Trie 使用字典树优化检索过程也是容易的，分别使用两棵 `Trie` 树来记录 $ss[i]$ 的前后缀，即正着存到 `tr1` 中，反着存到 `Tr2` 中。 > 还不了解 `Trie` 的同学可以先看前置 🧀：[实现 Trie (前缀树)](https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247488490&idx=1&sn=db2998cb0e5f08684ee1b6009b974089) 前置 🧀 通过图解形式讲解了 `Trie` 的结构与原理，以及提供了两种实现 `Trie` 的方式同时对于字典树的每个节点，我们使用数组 `idxs` 记录经过该节点的字符串 $ss[i]$ 所在 `ss` 中的下标 $i$，若某个字典树节点的索引数组 `tr.idxs` 为 $[a_1, a_2, ..., a_k]$ 则代表「从根节点到 `tr` 节点所对应的字符串」为 $ss[a_1], ss[a_2], ..., ss[a_k]$ 的前缀。这样我们可以即可在扫描前后缀 `a` 和 `b` 时，得到对应的候选下标列表 `l1` 和 `l2`，由于我们将 $ss[i]$ 添加到两棵 `tr` 中是按照下标「从小到大」进行，因此我们使用「双指针」算法分别从 `l1` 和 `l2` 结尾往后找到第一个共同元素即是答案（满足条件的最大下标）。 > 使用 `Trie` 优化后，`Java` 从 `TLE` 到 `AC`，`TypeScript` 耗时为原本的 $\frac{1}{7}$ ： ![](https://upload-images.jianshu.io/upload_images/1980848-c3f67d9ae1cead7b.png) Java 代码： ```Java class WordFilter { class TrieNode { TrieNode[] tns = new TrieNode[26]; List idxs = new ArrayList<>(); } void add(TrieNode p, String s, int idx, boolean isTurn) { int n = s.length(); p.idxs.add(idx); for (int i = isTurn ? n - 1 : 0; i >= 0 && i < n; i += isTurn ? -1 : 1) { int u = s.charAt(i) - 'a'; if (p.tns[u] == null) p.tns[u] = new TrieNode(); p = p.tns[u]; p.idxs.add(idx); } } int query(String a, String b) { int n = a.length(), m = b.length(); TrieNode p = tr1; for (int i = 0; i < n; i++) { int u = a.charAt(i) - 'a'; if (p.tns[u] == null) return -1; p = p.tns[u]; } List l1 = p.idxs; p = tr2; for (int i = m - 1; i >= 0; i--) { int u = b.charAt(i) - 'a'; if (p.tns[u] == null) return -1; p = p.tns[u]; } List l2 = p.idxs; n = l1.size(); m = l2.size(); for (int i = n - 1, j = m - 1; i >= 0 && j >= 0; ) { if (l1.get(i) > l2.get(j)) i--; else if (l1.get(i) < l2.get(j)) j--; else return l1.get(i); } return -1; } TrieNode tr1 = new TrieNode(), tr2 = new TrieNode(); public WordFilter(String[] ss) { int n = ss.length; for (int i = 0; i < n; i++) { add(tr1, ss[i], i, false); add(tr2, ss[i], i, true); } } public int f(String a, String b) { return query(a, b); } } ``` TypeScript 代码： ```TypeScript class TrieNode { tns: TrieNode[] = new Array() idxs: number[] = new Array() } class WordFilter { add(p: TrieNode, s: string, idx: number, isTurn: boolean): void { const n = s.length p.idxs.push(idx) for (let i = isTurn ? n - 1 : 0; i >= 0 && i < n; i += isTurn ? -1 : 1) { const u = s.charCodeAt(i) - 'a'.charCodeAt(0) if (p.tns[u] == null) p.tns[u] = new TrieNode() p = p.tns[u] p.idxs.push(idx) } } query(a: string, b: string): number { let n = a.length, m = b.length let p = this.tr1 for (let i = 0; i < n; i++) { const u = a.charCodeAt(i) - 'a'.charCodeAt(0) if (p.tns[u] == null) return -1 p = p.tns[u] } const l1 = p.idxs p = this.tr2 for (let i = m - 1; i >= 0; i--) { const u = b.charCodeAt(i) - 'a'.charCodeAt(0) if (p.tns[u] == null) return -1 p = p.tns[u] } const l2 = p.idxs n = l1.length; m = l2.length for (let i = n - 1, j = m - 1; i >= 0 && j >= 0; ) { if (l1[i] < l2[j]) j-- else if (l1[i] > l2[j]) i-- else return l1[i] } return -1 } tr1: TrieNode = new TrieNode() tr2: TrieNode = new TrieNode() constructor(ss: string[]) { for (let i = 0; i < ss.length; i++) { this.add(this.tr1, ss[i], i, false) this.add(this.tr2, ss[i], i, true) } } f(a: string, b: string): number { return this.query(a, b) } } ``` C++ 代码： ```C++ class WordFilter { public: struct TrieNode { TrieNode* tns[26] {nullptr}; vector idxs; }; void add(TrieNode* p, const string& s, int idx, bool isTurn) { int n = s.size(); p->idxs.push_back(idx); for(int i = isTurn ? n - 1 : 0; i >= 0 && i < n; i += isTurn ? -1 : 1) { int u = s[i] - 'a'; if(p->tns[u] == nullptr) p->tns[u] = new TrieNode(); p = p->tns[u]; p->idxs.push_back(idx); } } int query(const string& a, const string& b) { int n = a.size(), m = b.size(); auto p = tr1; for(int i = 0; i < n; i++) { int u = a[i] - 'a'; if(p->tns[u] == nullptr) return -1; p = p->tns[u]; } vector& l1 = p->idxs; p = tr2; for(int i = m - 1; i >= 0; i--) { int u = b[i] - 'a'; if(p->tns[u] == nullptr) return -1; p = p->tns[u]; } vector& l2 = p->idxs; n = l1.size(), m = l2.size(); for(int i = n - 1, j = m - 1; i >= 0 && j >= 0; ) { if(l1[i] > l2[j]) i--; else if(l1[i] < l2[j]) j--; else return l1[i]; } return -1; } TrieNode* tr1 = new TrieNode, *tr2 = new TrieNode; WordFilter(vector& ss) { int n = ss.size(); for(int i = 0; i < n; i++) { add(tr1, ss[i], i, false); add(tr2, ss[i], i, true); } } int f(string a, string b) { return query(a, b); } }; ``` * 时间复杂度：初始化操作复杂度为 $O(\sum_{i = 0}^{n - 1} ss[i].length)$，检索过程复杂度为 $O(a + b + n)$，其中 $a = b = 7$ 为前后缀的最大长度，$n = 1e4$ 为初始化数组长度，代表最多有 $n$ 个候选下标（注意：这里的 $n$ 只是粗略分析，实际上如果候选集长度越大的话，说明两个候选集是重合度是越高的，从后往前找的过程是越快结束的，可以通过方程算出一个双指针的理论最大比较次数 $k$，如果要将 $n$ 卡满成 $1e4$ 的话，需要将两个候选集设计成交替下标，此时 `f` 如果仍是 $1e4$ 次调用的话，必然会面临大量的重复查询，可通过引入 `map` 记录查询次数来进行优化） * 空间复杂度：$O(\sum_{i = 0}^{n - 1} ss[i].length)$ ## 最后这是我们「刷穿 LeetCode」系列文章的第 `No.745` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。更多更全更热门的「笔试/面试」相关资料可访问排版精美的 [合集新基地](https://www.acoier.com/archives/) 🎉🎉

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 210,914评论 6赞 490
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 89,935评论 2赞 383
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 156,531评论 0赞 345
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,309评论 1赞 282
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,381评论 5赞 384
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,730评论 1赞 289
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,882评论 3赞 404
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,643评论 0赞 266
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,095评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,448评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,566评论 1赞 339
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,253评论 4赞 328
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,829评论 3赞 312
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,715评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,945评论 1赞 264
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,248评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,440评论 2赞 348

【面试高频题】难度 3/5，字典树热门运用题

推荐阅读更多精彩内容