【面試高頻題】難度 3/5，字典樹熱門運用題

## 題目描述這是 LeetCode 上的 **[745. 前綴和后綴搜索](https://leetcode.cn/problems/prefix-and-suffix-search/solution/by-ac_oier-ayej/)** ，難度為 **困難**歌溉。 Tag : 「字典樹」設(shè)計一個包含一些單詞的特殊詞典朱灿，并能夠通過前綴和后綴來檢索單詞捆蜀。實現(xiàn) `WordFilter` 類： * `WordFilter(string[] words)` 使用詞典中的單詞 `words` 初始化對象。 * `f(string pref, string suff)` 返回詞典中具有前綴?`prefix`?和后綴 `suff`?的單詞的下標(biāo)轰传。如果存在不止一個滿足要求的下標(biāo)驴党，返回其中最大的下標(biāo) 。如果不存在這樣的單詞获茬，返回 $-1$ 港庄。示例： ``` 輸入 ["WordFilter", "f"] [[["apple"]], ["a", "e"]] 輸出 [null, 0] 解釋 WordFilter wordFilter = new WordFilter(["apple"]); wordFilter.f("a", "e"); // 返回 0 ，因為下標(biāo)為 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` 僅由小寫英文字母組成 * 最多對函數(shù) `f` 執(zhí)行 $10^4$ 次調(diào)用 ## 基本分析為了方便，我們令 `words` 為 `ss`佩谣，令 `pref` 和 `suff` 分別為 `a` 和 `b`把还。搜索某個前綴（后綴可看做是反方向的前綴）容易想到字典樹，但單詞長度數(shù)據(jù)范圍只有 $7$，十分具有迷惑性吊履，使用暴力做法最壞情況下會掃描所有的 $ss[i]$安皱，不考慮任何的剪枝操作的話，計算量也才為 $2 \times \ 7 \times 1e4 = 1.4 \times 10^5$艇炎，按道理是完全可以過的酌伊。但不要忘記 LC 是一個具有「設(shè)定每個樣例時長，同時又有總時長」這樣奇怪機制的 OJ缀踪。 ## 暴力（TLE or 雙百) 于是有了 `Java` 總時間超時居砖，`TypeScripe` 雙百的結(jié)果（應(yīng)該是 `TypeScript` 提交不多，同時設(shè)限寬松的原因）： ![](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 } } ``` * 時間復(fù)雜度：初始化操作復(fù)雜度為 $O(1)$驴娃，檢索操作復(fù)雜度為 $O(\sum_{i = 0}^{n - 1} ss[i].length)$ * 空間復(fù)雜度：$O(\sum_{i = 0}^{n - 1} ss[i].length)$ ## Trie 使用字典樹優(yōu)化檢索過程也是容易的奏候，分別使用兩棵 `Trie` 樹來記錄 $ss[i]$ 的前后綴，即正著存到 `tr1` 中唇敞，反著存到 `Tr2` 中鼻由。 > 還不了解 `Trie` 的同學(xué)可以先看前置 ??：[實現(xiàn) Trie (前綴樹)](https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247488490&idx=1&sn=db2998cb0e5f08684ee1b6009b974089) 前置 ?? 通過圖解形式講解了 `Trie` 的結(jié)構(gòu)與原理，以及提供了兩種實現(xiàn) `Trie` 的方式同時對于字典樹的每個節(jié)點厚棵，我們使用數(shù)組 `idxs` 記錄經(jīng)過該節(jié)點的字符串 $ss[i]$ 所在 `ss` 中的下標(biāo) $i$蕉世，若某個字典樹節(jié)點的索引數(shù)組 `tr.idxs` 為 $[a_1, a_2, ..., a_k]$ 則代表「從根節(jié)點到 `tr` 節(jié)點所對應(yīng)的字符串」為 $ss[a_1], ss[a_2], ..., ss[a_k]$ 的前綴。這樣我們可以即可在掃描前后綴 `a` 和 `b` 時婆硬，得到對應(yīng)的候選下標(biāo)列表 `l1` 和 `l2`狠轻，由于我們將 $ss[i]$ 添加到兩棵 `tr` 中是按照下標(biāo)「從小到大」進行，因此我們使用「雙指針」算法分別從 `l1` 和 `l2` 結(jié)尾往后找到第一個共同元素即是答案（滿足條件的最大下標(biāo)）彬犯。 > 使用 `Trie` 優(yōu)化后向楼，`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); } }; ``` * 時間復(fù)雜度：初始化操作復(fù)雜度為 $O(\sum_{i = 0}^{n - 1} ss[i].length)$谐区，檢索過程復(fù)雜度為 $O(a + b + n)$湖蜕，其中 $a = b = 7$ 為前后綴的最大長度，$n = 1e4$ 為初始化數(shù)組長度宋列，代表最多有 $n$ 個候選下標(biāo)（注意：這里的 $n$ 只是粗略分析昭抒，實際上如果候選集長度越大的話，說明兩個候選集是重合度是越高的炼杖，從后往前找的過程是越快結(jié)束的灭返，可以通過方程算出一個雙指針的理論最大比較次數(shù) $k$，如果要將 $n$ 卡滿成 $1e4$ 的話坤邪，需要將兩個候選集設(shè)計成交替下標(biāo)熙含，此時 `f` 如果仍是 $1e4$ 次調(diào)用的話，必然會面臨大量的重復(fù)查詢艇纺，可通過引入 `map` 記錄查詢次數(shù)來進行優(yōu)化） * 空間復(fù)雜度：$O(\sum_{i = 0}^{n - 1} ss[i].length)$ ## 最后這是我們「刷穿 LeetCode」系列文章的第 `No.745` 篇怎静，系列開始于 2021/01/01邮弹，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題蚓聘，我們將先把所有不帶鎖的題目刷完肠鲫。在這個系列文章里面，除了講解解題思路以外或粮，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應(yīng)的代碼模板捞高。為了方便各位同學(xué)能夠電腦上進行調(diào)試和提交代碼氯材，我建立了相關(guān)的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 。在倉庫地址里硝岗，你可以看到系列文章的題解鏈接氢哮、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解型檀。更多更全更熱門的「筆試/面試」相關(guān)資料可訪問排版精美的 [合集新基地](https://www.acoier.com/archives/) ????

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末冗尤，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子胀溺，更是在濱河造成了極大的恐慌裂七，老刑警劉巖，帶你破解...
沈念sama閱讀 216,496評論 6贊 501
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件仓坞，死亡現(xiàn)場離奇詭異背零，居然都是意外死亡，警方通過查閱死者的電腦和手機无埃，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,407評論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門徙瓶，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人嫉称，你說我怎么就攤上這事侦镇。” “怎么了织阅？”我有些...
開封第一講書人閱讀 162,632評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵壳繁，是天一觀的道長。經(jīng)常有香客問我荔棉，道長氮趋，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,180評論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任江耀，我火速辦了婚禮剩胁，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘祥国。我一直安慰自己昵观，他們只是感情好晾腔，可當(dāng)我...
茶點故事閱讀 67,198評論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著啊犬，像睡著了一般灼擂。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上觉至，一...
開封第一講書人閱讀 51,165評論 1贊 299
城市分裂傳說
那天剔应，我揣著相機與錄音，去河邊找鬼语御。笑死峻贮，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的应闯。我是一名探鬼主播纤控，決...
沈念sama閱讀 40,052評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼碉纺！你這毒婦竟也來了船万？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 38,910評論 0贊 274
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤骨田，失蹤者是張志新（化名）和其女友劉穎耿导，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體态贤，經(jīng)...
沈念sama閱讀 45,324評論 1贊 310
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡碎节，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,542評論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了抵卫。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片狮荔。...
茶點故事閱讀 39,711評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖介粘，靈堂內(nèi)的尸體忽然破棺而出殖氏，到底是詐尸還是另有隱情，我是刑警寧澤姻采，帶...
沈念sama閱讀 35,424評論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布雅采，位于F島的核電站，受9級特大地震影響慨亲，放射性物質(zhì)發(fā)生泄漏婚瓜。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,017評論 3贊 326
男人毒藥：我在死后第九天來索命
文/蒙蒙一刑棵、第九天我趴在偏房一處隱蔽的房頂上張望巴刻。院中可真熱鬧，春花似錦蛉签、人聲如沸胡陪。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,668評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽柠座。三九已至邑雅，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間妈经，已是汗流浹背淮野。一陣腳步聲響...
開封第一講書人閱讀 32,823評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留吹泡，地道東北人骤星。一個月前我還...
沈念sama閱讀 47,722評論 2贊 368
代替公主和親
正文我出身青樓，卻偏偏與公主長得像荞胡，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子了嚎，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 44,611評論 2贊 353

【面試高頻題】難度 3/5，字典樹熱門運用題

推薦閱讀更多精彩內(nèi)容