面試場上被問到“你項(xiàng)目里的搜索聯(lián)想是怎么做的”很多人的第一反應(yīng)是拉倒排索引。其實(shí)在數(shù)據(jù)規(guī)模不大、只想快速支持前綴匹配的場景里一棵前綴樹Trie往往更直接。LeetCode 208這道題——實(shí)現(xiàn)Trie前綴樹常年霸占熱門100題榜單幾乎所有刷題路線圖都會(huì)把字符串專題的起點(diǎn)放在這里。它代碼不長卻把數(shù)據(jù)結(jié)構(gòu)的幾個(gè)關(guān)鍵設(shè)計(jì)一次性全考到節(jié)點(diǎn)怎么定義、孩子的映射用數(shù)組還是哈希、詞尾怎么標(biāo)記、search和startsWith到底哪里不同。寫這篇文章時(shí)我一邊復(fù)盤自己當(dāng)年提交時(shí)翻過的車一邊把原理、模板、邊界測(cè)試都整理清楚。適合剛開始刷字符串題的新手也適合要把這題當(dāng)模板往211、212進(jìn)階的讀者。1. 面對(duì)前綴樹題目先想清楚它在解決什么問題1.1 為什么普通集合做不到高效前綴匹配如果不考慮前綴樹只要求“存單詞”和“查單詞”一個(gè)哈希集合就夠了set()存下所有字符串插入和精確查找的時(shí)間都是 O(len(word))簡單、直接、不容易出錯(cuò)。可一旦需求變成“查所有以某個(gè)前綴開頭的單詞”哈希集合的短板立刻暴露出來——你只能把詞典里每一個(gè)單詞都拿出來逐個(gè)調(diào)用word.startswith(prefix)整個(gè)查詢耗時(shí)和詞典規(guī)模成正比。打個(gè)比方哈希集合像一箱散裝卡片每張卡片寫著一個(gè)單詞你要找所有以app開頭的卡片只能一張張翻。而前綴樹像一本按字母順序排好的電話簿你把a(bǔ)pp三個(gè)字母按順序走下來自然就到了所有app開頭的單詞所在的那一疊根本不需要碰其他卡片。Trie 的核心思想就是按字符拆分單詞讓擁有公共前綴的單詞共享路徑。apple和app會(huì)共享a - p - p這一段只有到第四個(gè)字符才分叉。application和apple同樣先共享a - p - p - l到i和e才分開。整個(gè)結(jié)構(gòu)相當(dāng)于是把字符串集合的前綴信息壓縮進(jìn)了一棵多叉樹里。這種結(jié)構(gòu)帶來的直接收益是查詢一個(gè)前綴是否存在的復(fù)雜度只取決于前綴長度而不是詞典里有多少個(gè)單詞。對(duì)于一個(gè) 10 萬詞的詞典哈希集合做一次前綴掃描最壞要比較 10 萬個(gè)單詞Trie 只需要走 prefix 長度那么多步。1.2 LeetCode 208 真正想考察的設(shè)計(jì)點(diǎn)LeetCode 208 的要求非常明確實(shí)現(xiàn)一個(gè)Trie類支持insert(word)、search(word)、startsWith(prefix)三個(gè)操作。因?yàn)轭}目給的是英文小寫字母所以它本質(zhì)上是在考察三件事節(jié)點(diǎn)對(duì)象怎么定義。每個(gè)節(jié)點(diǎn)需要保存什么信息才能讓整棵樹跑起來子節(jié)點(diǎn)集合怎么組織。定長數(shù)組、哈希表還是別的映射方式不同選擇的成本在哪里詞尾怎么標(biāo)記。search(app)和startsWith(app)在 Trie 上走的路一模一樣為什么返回的結(jié)果不一樣答案就差在一個(gè)小小的標(biāo)記位上。這題在熱門 100 題里的地位很特殊它本身不涉及復(fù)雜的遞歸、貪心、動(dòng)態(tài)規(guī)劃但它是一個(gè)“地基題”。你會(huì)發(fā)現(xiàn)后續(xù)一堆高頻題比如 211. 添加與搜索單詞、212. 單詞搜索 II、648. 單詞替換都是在 Trie 的基礎(chǔ)上疊加新的邏輯?；A(chǔ)結(jié)構(gòu)沒寫對(duì)后面的題目寸步難行。還有一點(diǎn)值得注意面試官往往不滿足于只讓你把這版代碼寫對(duì)還會(huì)追加“如何支持刪除”“如何統(tǒng)計(jì)詞頻”“如何返回聯(lián)想詞”這類擴(kuò)展問題。如果一開始就對(duì)節(jié)點(diǎn)的設(shè)計(jì)理得夠清楚這些追問都能順手接住。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)孩子節(jié)點(diǎn)與詞尾標(biāo)記2.1 孩子集合用定長數(shù)組還是哈希表先把最常見的兩種節(jié)點(diǎn)結(jié)構(gòu)擺出來大家感受一下區(qū)別。定長數(shù)組版適合字符集固定且已知class Trie: def __init__(self): self.children [None] * 26 # 每個(gè)位置對(duì)應(yīng)一個(gè)字母 a-z self.is_end False哈希表版適合字符范圍大或不確定class TrieNode: def __init__(self): self.children {} # 字符 - TrieNode self.is_end False這兩個(gè)版本沒有絕對(duì)的好壞完全看場景。定長數(shù)組的思路是已知只有 26 個(gè)小寫字母那就給每個(gè)節(jié)點(diǎn)開一個(gè)長度為 26 的數(shù)組索引 0 對(duì)應(yīng)a索引 25 對(duì)應(yīng)z。要判斷當(dāng)前節(jié)點(diǎn)有沒有孩子c只需要計(jì)算ord(c) - ord(a)得到下標(biāo)然后看children[index]是不是None。訪問速度是嚴(yán)格的 O(1)不會(huì)出現(xiàn)哈希沖突也不會(huì)因?yàn)樽址唇赢a(chǎn)生額外的存儲(chǔ)開銷。代價(jià)是空間。哪怕當(dāng)前節(jié)點(diǎn)只有一個(gè)孩子也要付出 26 個(gè)指針的空間。如果字符集擴(kuò)大到大寫字母、數(shù)字、中文甚至 URL 中的/、.、-定長數(shù)組就得跟著擴(kuò)大擴(kuò)大到幾千上萬個(gè)字符后絕大多數(shù)節(jié)點(diǎn)只用到其中幾個(gè)位置內(nèi)存浪費(fèi)非常嚴(yán)重。哈希表的做法則是“用多少開多少”。children字典里只有實(shí)際存在的字符才有鍵字符集無論多大都能支持寫起來也更通用。缺點(diǎn)是每個(gè)節(jié)點(diǎn)多了一個(gè)字典對(duì)象每次訪問孩子都比數(shù)組下標(biāo)慢一點(diǎn)而且哈希表本身也有額外的內(nèi)存開銷。所以當(dāng)題目明確限制為 26 個(gè)小寫字母時(shí)數(shù)組版本是絕對(duì)的首選代碼清晰、查詢快、面試官也愛看。在 Java/C 這類語言里數(shù)組版還能進(jìn)一步用Trie[] children new Trie[26]來表示配合null判斷語義非常直觀。Python 里用[None] * 26也差不多。2.2 is_end 標(biāo)記為什么省不得這是最容易被新手忽略的設(shè)計(jì)點(diǎn)Trie 的節(jié)點(diǎn)要區(qū)分“這中間路過的節(jié)點(diǎn)”和“這是一個(gè)完整單詞的終點(diǎn)”。舉個(gè)例子插入apple之后整棵樹里肯定存在a - p - p - l - e這條路徑。如果這時(shí)調(diào)用search(app)按字符串走也能走到一個(gè)節(jié)點(diǎn)總不能直接返回true吧app并不是我們插入過的單詞只是apple的公共前綴。is_end標(biāo)記就是為了解決這個(gè)問題。在插入流程的最后一步把結(jié)束節(jié)點(diǎn)的is_end設(shè)為True表示“這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的是一個(gè)完整單詞的結(jié)尾”。如果后來又把a(bǔ)pp也插進(jìn)去那么在第二次插入時(shí)走到原來apple路徑的第三個(gè)節(jié)點(diǎn)把這個(gè)節(jié)點(diǎn)的is_end也設(shè)為True即可。這個(gè)設(shè)計(jì)很像書目錄里的頁碼和正文的關(guān)系。app出現(xiàn)在目錄索引里說明它被單獨(dú)收錄了app只是apple的中間幾個(gè)字母說明它只是正文里的一部分不能當(dāng)成獨(dú)立詞條。is_end就是維護(hù)這個(gè)“是否獨(dú)立成詞”信息的開關(guān)。另外如果你以后想支持“統(tǒng)計(jì)每個(gè)單詞出現(xiàn)了多少次”可以把is_end從布爾值升級(jí)成整數(shù)count插入時(shí)每次都count 1查詢時(shí)返回對(duì)應(yīng)節(jié)點(diǎn)的count。原理完全一樣只是把開關(guān)變成了計(jì)數(shù)器。3. 三個(gè)核心方法逐一落地3.1 insert沿著字符路徑一路走到尾插入單詞的流程只有三步從根節(jié)點(diǎn)出發(fā)逐個(gè)字符往下走遇到不存在的孩子節(jié)點(diǎn)就新建走完整個(gè)單詞后打上is_end標(biāo)記。class Trie: def __init__(self): self.children [None] * 26 self.is_end False def insert(self, word: str) - None: node self for ch in word: idx ord(ch) - ord(a) if node.children[idx] is None: node.children[idx] Trie() node node.children[idx] node.is_end True這里要特別留意node node.children[idx]這一步。很多第一次寫的人容易在if里新建完節(jié)點(diǎn)后忘記把當(dāng)前指針移過去導(dǎo)致后續(xù)字符全部掛在根節(jié)點(diǎn)上整棵樹變成一個(gè)畸形的“星形結(jié)構(gòu)”。實(shí)際上 Trie 的遍歷邏輯和鏈表非常像鏈表通過node node.next前進(jìn)Trie 通過node node.children[idx]前進(jìn)只是在每個(gè)節(jié)點(diǎn)上按字符選擇走哪條分支而已。重復(fù)插入同一個(gè)單詞也沒問題。第二次插入時(shí)路徑上的節(jié)點(diǎn)都已存在循環(huán)直接一路走到底最后再設(shè)置一次is_end True結(jié)果冪等。插入一個(gè)新詞也只需要?jiǎng)?chuàng)建它獨(dú)有的那部分路徑對(duì)已有公共前綴零影響。3.2 search、startsWith共同的查找邏輯與一處關(guān)鍵差異search和startsWith的前半段動(dòng)作完全一樣從根節(jié)點(diǎn)出發(fā)沿著單詞字符往下走如果中間任何一個(gè)孩子節(jié)點(diǎn)不存在直接返回失敗如果整個(gè)串都走完了說明前綴路徑一定存在于樹中。兩者的差異只在最后一步search(word)還要確認(rèn)當(dāng)前位置是一個(gè)單詞的結(jié)尾即node.is_end True。startsWith(prefix)不關(guān)心詞尾只要能走完前綴就算成功。為了讓邏輯不重復(fù)我把“按照字符串走到對(duì)應(yīng)節(jié)點(diǎn)”的公共部分抽成一個(gè)輔助函數(shù)_find_node。這樣搜索和前綴查詢都能復(fù)用而且后續(xù)如果要加delete操作也可以直接調(diào)用這個(gè) helper 定位目標(biāo)節(jié)點(diǎn)。def _find_node(self, prefix: str): node self for ch in prefix: idx ord(ch) - ord(a) if node.children[idx] is None: return None node node.children[idx] return node def search(self, word: str) - bool: node self._find_node(word) return node is not None and node.is_end def startsWith(self, prefix: str) - bool: return self._find_node(prefix) is not Nonesearch和startsWith看似只差一個(gè)and node.is_end但漏掉這個(gè)判斷是這題最常見的提交錯(cuò)誤之一。后面我在常見問題里會(huì)專門展開。這里還有一個(gè)“為什么_find_node返回None就萬事大吉”的細(xì)節(jié)當(dāng)某個(gè)字符不存在時(shí)說明字典里根本沒有任何以該字符串為開頭的單詞后續(xù)也不用繼續(xù)查了。返回None給上層search和startsWith自然得到False。3.3 完整代碼與本地測(cè)試把上面幾段拼起來就是一份可以直接運(yùn)行的 LeetCode 208 代碼class Trie: def __init__(self): self.children [None] * 26 self.is_end False def insert(self, word: str) - None: node self for ch in word: idx ord(ch) - ord(a) if node.children[idx] is None: node.children[idx] Trie() node node.children[idx] node.is_end True def search(self, word: str) - bool: node self._find_node(word) return node is not None and node.is_end def startsWith(self, prefix: str) - bool: return self._find_node(prefix) is not None def _find_node(self, prefix: str): node self for ch in prefix: idx ord(ch) - ord(a) if node.children[idx] is None: return None node node.children[idx] return node本地驗(yàn)證的時(shí)候別只跑題目給的簡單樣例。我的習(xí)慣是自己手寫一組覆蓋典型邊界的用例obj Trie() obj.insert(apple) assert obj.search(apple) is True # 完整詞 assert obj.search(app) is False # 是前綴不是完整詞 assert obj.startsWith(app) is True # 前綴查詢成功 obj.insert(app) assert obj.search(app) is True # 插入后變成完整詞 assert obj.search(apple) is True # 已有詞不受影響 assert obj.startsWith(appl) is True # 中間前綴 assert obj.startsWith(b) is False # 不存在的分支這組細(xì)碎用例跑通了提交基本不會(huì)出問題。我當(dāng)年刷這道題時(shí)先自己寫了個(gè) 26 字母數(shù)組版然后故意寫了幾個(gè)錯(cuò)誤版本來比較結(jié)果比如忘記is_end的版本、search直接復(fù)用startsWith的版本。通過這種“故意寫錯(cuò)再對(duì)照”的訓(xùn)練對(duì) Trie 的語義理解會(huì)深刻很多。4. 復(fù)雜度推導(dǎo)與工程里的應(yīng)用真相4.1 時(shí)間、空間復(fù)雜度到底牛在哪里Trie 的時(shí)間復(fù)雜度非常簡潔insertO(len(word))需要遍歷單詞的每個(gè)字符。searchO(len(word))同樣只遍歷一次。startsWithO(len(prefix))只看前綴長度。不論詞典里有 100 個(gè)單詞還是 1 億個(gè)單詞這些操作都只需要從根節(jié)點(diǎn)走一條路徑跟總單詞量無關(guān)。這是它對(duì)比哈希集合在“前綴查詢”場景下的核心優(yōu)勢(shì)?？臻g上Trie 的最差情況是不存在任何公共前綴每個(gè)單詞的每個(gè)字符都新建一個(gè)節(jié)點(diǎn)這時(shí)節(jié)點(diǎn)總數(shù)等于所有單詞長度之和。但實(shí)際應(yīng)用中因?yàn)榇罅繂卧~共享前綴節(jié)點(diǎn)數(shù)會(huì)遠(yuǎn)小于這個(gè)上界。舉例來說插入apple、app、application這三個(gè)詞獨(dú)立存儲(chǔ)需要 18 個(gè)字符Trie 只需要a p p l ei c a t i o n這條路徑上的節(jié)點(diǎn)總共 13 個(gè)節(jié)點(diǎn)中間還復(fù)用了 5 個(gè)節(jié)點(diǎn)。不過數(shù)組版 Trie 有一個(gè)不能忽略的工程問題每個(gè)節(jié)點(diǎn)固定存 26 個(gè)孩子指針無論它實(shí)際有幾個(gè)孩子。一個(gè)字符串很長但每個(gè)節(jié)點(diǎn)只有一個(gè)孩子時(shí)內(nèi)存開銷就是“字符串長度 × 26 個(gè)指針”。面對(duì)海量數(shù)據(jù)壓縮 Trie、Radix Tree 或者用哈希表省空間的方案會(huì)更實(shí)用。算法題里通常不會(huì)糾結(jié)這個(gè)但真實(shí)系統(tǒng)設(shè)計(jì)時(shí)一定要算清楚。4.2 Trie 在真實(shí)系統(tǒng)里不只是“詞典”這題雖然以 LeetCode 題目的形式存在但 Trie 在工程中的出鏡率相當(dāng)高。最典型的就是輸入框自動(dòng)補(bǔ)全。搜索框、IDE 的代碼提示、命令行的 tab 補(bǔ)全本質(zhì)上都是“輸入前綴返回候選詞”。典型實(shí)現(xiàn)會(huì)在 Trie 節(jié)點(diǎn)上額外存儲(chǔ)“以當(dāng)前節(jié)點(diǎn)為前綴的 Top K 熱詞列表”用戶每敲入一個(gè)字符就沿著 Trie 走一步然后直接取出候選列表非常快。拼寫糾錯(cuò)也是經(jīng)典場景。當(dāng)用戶輸入的單詞在字典里精確匹配失敗時(shí)可以用 BFS 或動(dòng)態(tài)規(guī)劃在 Trie 上計(jì)算編輯距離找到相近的正確單詞。比遍歷全量詞典再算編輯距離高效得多。網(wǎng)絡(luò)領(lǐng)域里的路由表最長前綴匹配從思想上看也類似 Trie 的變體路由表把 IP 地址按二進(jìn)制位展開成一棵二叉前綴樹查找時(shí)按最長匹配規(guī)則選擇出口。它和圖論中的二叉 Trie 幾乎是一回事。還有一類高頻工程場景是敏感詞過濾和詞庫匹配。經(jīng)典的 AC 自動(dòng)機(jī)Aho-Corasick本質(zhì)上就是 Trie 加失敗指針先在 Trie 中構(gòu)建所有敏感詞再給每個(gè)節(jié)點(diǎn)補(bǔ)充 fail 指針使得掃描文本時(shí)能在一次遍歷內(nèi)匹配出所有詞條。這個(gè)算法廣泛用于內(nèi)容安全、日志關(guān)鍵字過濾等領(lǐng)域。理解 208對(duì)理解 AC 自動(dòng)機(jī)是很大的助益。順帶一提把 Trie 的字符從英文換成二進(jìn)制位就變成了01 字典樹可以用來高效解決最大異或值匹配的問題比如 LeetCode 421 求數(shù)組中兩個(gè)數(shù)的最大異或值。這樣看下來Trie 確實(shí)是一塊非常通用的結(jié)構(gòu)底盤。5. 常見翻車點(diǎn)與進(jìn)階題串講5.1 提交記錄里出現(xiàn)最多的 5 類錯(cuò)誤下面這幾種錯(cuò)誤我見過太多次也親手犯過整理成一張速查表給大家參考錯(cuò)誤類型具體表現(xiàn)正確處理忘記設(shè)置is_endinsert(app)后search(app)返回False插入循環(huán)結(jié)束后一定要執(zhí)行node.is_end Truesearch誤用startsWith邏輯只判斷能不能走完路徑不校驗(yàn)詞尾search(app)誤報(bào)Truesearch必須同時(shí)滿足node is not None and node.is_end數(shù)組越界輸入包含大寫字母或其他字符時(shí)直接ord(ch) - ord(a)得負(fù)數(shù)或越界題目約束小寫字母時(shí)默認(rèn)安全擴(kuò)展場景改用哈希表或先統(tǒng)一轉(zhuǎn)小寫節(jié)點(diǎn)指針沒往下走插入時(shí)新建了孩子節(jié)點(diǎn)卻忘了node node.children[idx]所有字符都掛在根節(jié)點(diǎn)下每次循環(huán)結(jié)尾必須更新node為當(dāng)前字符對(duì)應(yīng)的孩子節(jié)點(diǎn)把實(shí)例變量寫成類變量在類屬性里定義children [None] * 26導(dǎo)致多個(gè) Trie 對(duì)象共享同一個(gè)孩子列表所有可變數(shù)據(jù)都在__init__中初始化第一類錯(cuò)誤尤其隱蔽因?yàn)樗奶卣骱苊黠@卻很難一眼看出來insert(apple)之后search(apple)正常返回True因?yàn)閍pple的最后一個(gè)節(jié)點(diǎn)恰好是循環(huán)結(jié)束時(shí)node停留的位置但由于沒寫is_end True這個(gè)節(jié)點(diǎn)始終是普通中間節(jié)點(diǎn)。如果只測(cè)試完整單詞這個(gè) Bug 會(huì)被掩蓋直到你測(cè)試“先插入apple再查詢app”這種場景問題才會(huì)暴露search(app)走到的節(jié)點(diǎn)明明存在但它不是詞尾返回False才對(duì)——可沒寫is_end的代碼里所有節(jié)點(diǎn)看起來都不是詞尾于是search(apple)也會(huì)變成False。另一種讓人頭疼的情況是多個(gè)測(cè)試用例之間互相污染。如果你在 LeetCode 之外自己寫測(cè)試幾個(gè)獨(dú)立的測(cè)試樣例共用一個(gè)Trie對(duì)象前一個(gè)用例插入的詞會(huì)影響后一個(gè)用例的查詢結(jié)果。正確做法是每個(gè)測(cè)試用例都重新Trie()一次或者在類內(nèi)部提供清空方法。5.2 掌握這題之后可以順路干掉哪些題LeetCode 208 只是起點(diǎn)接下來的進(jìn)階路徑非常清晰211. 添加與搜索單詞在 Trie 的基礎(chǔ)上支持.通配符搜索時(shí)遇到.就要遍歷當(dāng)前節(jié)點(diǎn)的所有孩子本質(zhì)上是在樹上做 DFS。理解了 208 的結(jié)構(gòu)211 只需要一個(gè)遞歸函數(shù)就能搞定。212. 單詞搜索 II給定一個(gè)字符網(wǎng)格和一組單詞找出網(wǎng)格中能拼出的所有單詞。做法是先拿所有單詞建 Trie再在網(wǎng)格上做回溯 DFS遞歸過程中一旦發(fā)現(xiàn)當(dāng)前路徑不是任何 Trie 節(jié)點(diǎn)的前綴路徑就立刻剪枝。這題如果沒有 Trie暴力匹配會(huì)超時(shí)。648. 單詞替換給定一個(gè)詞典把句子中所有以詞典詞為前綴的單詞替換成該前綴詞。解法是先建 Trie再檢查句子中的每個(gè)單詞能否在 Trie 里找到第一個(gè)is_end為 true 的路徑終點(diǎn)。745. 前綴和后綴搜索同時(shí)要求前綴和后綴匹配常見的處理方式是用兩個(gè) Trie一個(gè)正常插入單詞另一個(gè)插入反轉(zhuǎn)后的單詞查詢時(shí)把前綴和后綴分別在兩棵樹上匹配。這四道題只要刷完一遍你會(huì)發(fā)現(xiàn)它們?nèi)坷@不開一個(gè)核心能力在 Trie 上沿著字符路徑移動(dòng)同時(shí)根據(jù)is_end做判斷。208 中的_find_nodehelper 在這些題里也會(huì)反復(fù)出現(xiàn)只是有的題需要把它擴(kuò)展成遞歸版。如果你時(shí)間充裕還可以再補(bǔ)幾道“Trie 思維遷移”題比如421. 數(shù)組中兩個(gè)數(shù)的最大異或值它把字符 child 換成了二進(jìn)制位 child0/1本質(zhì)上還是同一套結(jié)構(gòu)。1351之類的網(wǎng)格題就算了不是同一類路線。真正值得精力的是把 211、212、648、745 這四條分支走通比盲目刷題有用得多。最后分享一個(gè)我實(shí)際刷題時(shí)養(yǎng)成的小習(xí)慣寫完 Trie不要只跑題里的樣例至少在本地跑一遍insert(apple)、search(app)、search(apple)、startsWith(app)、insert(app)、search(app)這組用例再提交。我見過太多人把search和startsWith的差異想通了卻在is_end上翻車。數(shù)據(jù)結(jié)構(gòu)題拿到手后先在本地把“能走通但語義不同”的邊界測(cè)一遍比直接提交等判題機(jī)反饋要省心得多。這就是我每次做字符串系列題都會(huì)保留的底線操作。