1. 項目概述與思路拆解1.1 一個看起來簡單卻暗藏玄機的題目你有沒有想過為什么搜索引擎輸入幾個字符就能立刻給出完整的建議詞手機通訊錄里輸入“zhang”就能把所有姓張的聯(lián)系人拉出來這些體驗背后都站著一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)——Trie樹也叫前綴樹。LeetCode第208題要求我們自己動手實現(xiàn)一個Trie包含插入、查找、前綴匹配三個核心操作。我第一次看到這道題時第一反應(yīng)是“這不就是個樹形結(jié)構(gòu)嘛有什么難的”。但實際上手之后發(fā)現(xiàn)Trie的實現(xiàn)雖然代碼量不大但對數(shù)據(jù)結(jié)構(gòu)的理解要求相當高。你不僅要設(shè)計出合理的節(jié)點結(jié)構(gòu)還要想清楚每個方法之間的邏輯關(guān)系甚至要能解釋清楚為什么這種結(jié)構(gòu)在字符串搜索場景下效率遠高于哈希表和二叉樹。這也是為什么這道題被列入LeetCode熱門100題幾乎年年出現(xiàn)在各大公司的算法面試中周賽前補題時也經(jīng)常有人拿它來復(fù)習基礎(chǔ)。1.2 為什么需要Trie而不是其他數(shù)據(jù)結(jié)構(gòu)要理解Trie的價值先得看清其他選手的短板。用哈希表存字典查詢某個完整單詞確實是O(1)但它只能做“完全匹配”根本做不了前綴匹配。比如我們要查所有以“pre”開頭的單詞哈希表只能把整個字典掃描一遍效率堪憂。用二叉搜索樹存儲字符串查找和插入都是O(LlogN)的復(fù)雜度其中L是字符串長度N是單詞數(shù)量雖然能支持有序遍歷但在前綴匹配場景下依然需要頻繁的回溯和比較實際表現(xiàn)并不理想。Trie的核心思路是利用字符串之間的公共前綴來減少存儲空間和查詢時間。它把每個字符作為一條邊從根節(jié)點出發(fā)順著字符一路走下來就能找到一個單詞。想象一下把“apple”和“app”都存進Trie它們共享“app”這條路徑只是在節(jié)點上標記一下“app”是否是一個完整單詞。這種結(jié)構(gòu)天然支持前綴匹配——只要沿著前綴路徑走一遍路徑終點下面的所有分支就是所有匹配的單詞。用生活化的比喻來說Trie就像一本按前幾級目錄分類擺放的百科全書。你要找“計算機科學”相關(guān)的所有內(nèi)容不需要一頁頁翻只需要走到“計”字的分區(qū)再走到“算”字的分區(qū)后面所有分支就是你要找的內(nèi)容。哈希表則是把每本書隨便扔進一個編號箱子里找單本很快但想按主題批量找就得把所有箱子都打開看一眼。1.3 解題關(guān)鍵詞與題目核心要求這道題的官方描述很簡潔實現(xiàn)一個包含insert、search、startsWith三種方法的數(shù)據(jù)結(jié)構(gòu)?？雌饋砗唵蔚袔讉€隱含的考察點容易被人忽略。enter第一個是單詞可能包含重復(fù)插入的情況連續(xù)兩次insert同一個單詞不應(yīng)該影響后續(xù)search的判斷。enter第二個是空字符串的處理LeetCode的測試用例里會考察插入空串的情況此時根節(jié)點本身就需要被標記為“是一個單詞的結(jié)尾”。第三個是字符集的范圍本題默認輸入全為小寫英文字母共26個字符這直接決定了節(jié)點里孩子數(shù)組的固定長度為26不需要用哈希表來動態(tài)管理子節(jié)點這也是很多新手容易糾結(jié)的地方。如果你去翻leetcode題解區(qū)會發(fā)現(xiàn)大多數(shù)人都用固定數(shù)組的方式實現(xiàn)原因很簡單字母范圍固定且連續(xù)用數(shù)組按下標訪問是最快的方案還能省去哈希函數(shù)計算的開銷。但如果在通用場景下比如需要支持Unicode字符集固定數(shù)組就會造成巨大的內(nèi)存浪費這個時候就應(yīng)該換成HashMap來存儲孩子節(jié)點。這個取舍思路在后文中我會專門展開聊。2. 核心原理Trie樹的數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)細節(jié)2.1 Trie節(jié)點的設(shè)計一場關(guān)于內(nèi)存和速度的權(quán)衡Trie的核心就是它的節(jié)點類。每個節(jié)點只需要做兩件事記錄從根節(jié)點到當前節(jié)點的路徑是否是一個完整單詞以及存儲通向下一層節(jié)點的指針。代碼原型非常簡單class TrieNode { TrieNode[] children new TrieNode[26]; boolean isEnd; }但真正落地時這里的每一個細節(jié)都有講究。children數(shù)組用26個元素是因為題目明確說輸入只有小寫英文字母。把字符c換算成數(shù)組下標只需要做一個簡單的減法c - a。這個映射關(guān)系是固定的一一對應(yīng)所以查詢孩子節(jié)點就變成了一次數(shù)組訪問時間復(fù)雜度O(1)。有人可能會問為什么不直接用MapCharacter, TrieNode來存孩子那樣代碼看起來更“通用”也不用考慮數(shù)組越界的問題。但從性能角度考量HashMap涉及哈希計算和可能的鏈表遍歷實際運行時開銷遠高于數(shù)組直接尋址。再者在LeetCode刷題這個場景下輸入永遠是26個小寫字母用數(shù)組是最貼合約束條件的選擇。如果你看過一些Python的題解很多人會直接用dict來存那是因為Python的列表在動態(tài)擴容上有些劣勢而Java和C更適合用固定數(shù)組。語言特性會影響局部決策這本身就是算法面試中值得展示的分析能力。接下來是isEnd這個布爾字段。它解決的是“路徑相同但單詞不同”的問題。舉個例子先插入app再插入apple。這兩個單詞共享a-p-p這條路徑那么當我們在app的最后一個p節(jié)點上進行標記時它既是app的終點又是通向apple的中間節(jié)點。如果沒有isEnd標記搜索app時我們會走到這個節(jié)點卻不知道它是不是一個合法單詞就會出現(xiàn)找不到的尷尬情況。關(guān)于節(jié)點初始化也有一個常見的坑new TrieNode()的時候數(shù)組默認元素是null這是正常的不需要也不應(yīng)該預(yù)先創(chuàng)建所有子節(jié)點。只有當你真正需要插入某個字符時才去創(chuàng)建對應(yīng)的子節(jié)點對象。這種懶加載思路是Trie節(jié)約內(nèi)存的關(guān)鍵。如果一上來就為每個節(jié)點創(chuàng)建26個子節(jié)點那插入第一個單詞a之后整棵樹里就有27個節(jié)點存在相當浪費。2.2 從遞歸思維到迭代操作理解了節(jié)點結(jié)構(gòu)我們就可以來看三個核心操作了。其實Trie的每個操作都能用遞歸實現(xiàn)但在實際刷題中迭代版本更直觀也更好Debug。先看插入操作。我們需要沿著單詞的每個字符走一遍Trie遇到不存在的節(jié)點就新建走到最后一個字符時把該節(jié)點的isEnd置為true。代碼實現(xiàn)如下public void insert(String word) { TrieNode node root; for (char c : word.toCharArray()) { int idx c - a; if (node.children[idx] null) { node.children[idx] new TrieNode(); } node node.children[idx]; } node.isEnd true; }注意一個細節(jié)這里我們是用一個游標節(jié)點node不斷向下移動而不是遞歸地調(diào)用insert方法。遞歸寫法雖然也能實現(xiàn)而且看起來“更優(yōu)雅”但多了一層函數(shù)調(diào)用開銷而且參數(shù)傳遞要額外帶上當前遍歷到的深度代碼反而更繞。迭代寫法的優(yōu)勢在于整個流程就是“指針移動然后判斷空位”非常接近我們對樹的高度直觀理解。搜索一個完整單詞時核心邏輯是“能走通路徑且路徑終點有單詞標記”。而前綴匹配的邏輯是“能走通路徑”就行不需要看isEnd。這兩個操作高度相似所以我們可以抽出一個公共方法把走到字符串對應(yīng)的節(jié)點這個邏輯統(tǒng)一起來。如果不這樣做search和startsWith里會重復(fù)兩段幾乎一樣的循環(huán)代碼這在面試中屬于典型的“可以優(yōu)化但容易被忽視”的扣分點。2.3 復(fù)雜度分析到底快在哪既然算法面試離不開復(fù)雜度分析我們也用數(shù)學方法拆一下Trie的時間與空間開銷。設(shè)單詞平均長度為L字典中單詞數(shù)量為N字符集大小為K此處K26。2.3.1 時間復(fù)雜度插入每次插入要遍歷單詞的每個字符最多創(chuàng)建L個節(jié)點所以時間復(fù)雜度是O(L)。如果單詞在路徑上已存在則無需新建節(jié)點只需移動指針即可同樣要走L步。搜索完整單詞同樣要遍歷單詞長度L每一步做一次數(shù)組訪問。如果路徑斷了提前返回false但最壞情況下還是要走完L步復(fù)雜度O(L)。前綴匹配和搜索類似最壞也是O(L)。因為K是常數(shù)26而在每一層查找下一個孩子節(jié)點時用的是數(shù)組直接尋址所以這里的O(L)里不含logK因子。比較一下其他方案哈希表在搜索完整單詞時是O(L)計算哈希也要遍歷每個字符但前綴匹配時哈希表無能為力只能O(N*L)暴力掃表。而二叉樹搜索字符串的復(fù)雜度是O(LlogN)N很大時差距明顯。Trie把時間消耗和單詞長度綁定和詞典規(guī)模基本無關(guān)這是它在大規(guī)模詞典場景下的一大優(yōu)勢。2.3.2 空間復(fù)雜度Trie的空間開銷是最容易出現(xiàn)爭議的地方。最壞情況下如果N個單詞之間沒有任何公共前綴比如所有單詞首字母都不同那么總的節(jié)點數(shù)約為NL。每個節(jié)點包含一個長度為26的數(shù)組在Java中對象引用數(shù)組本身約104字節(jié)再加上對象的固定頭部開銷所以總內(nèi)存可能達到NL*104字節(jié)。一旦單詞數(shù)量級到達百萬內(nèi)存就會噴得很厲害。但在實際場景中單詞之間大量共享前綴Trie的存儲效率優(yōu)于把所有單詞獨立存儲。比如存儲apple和appTrie只需要5個節(jié)點而富文本存儲需要兩個完整的字符串。Trie是用空間換時間、用共享前綴換存儲的例子。面試時能講清楚這一點說明你真的理解了這種數(shù)據(jù)結(jié)構(gòu)的取舍邏輯。2.4 兩種遍歷方向與前置知識的補充如果你之前接觸過二叉樹可能會覺得Trie有點跳躍。這里補一個基礎(chǔ)概念普通二叉樹每個節(jié)點最多有兩個孩子而Trie每個節(jié)點最多有K個孩子K是字符集大小。從這個角度來說Trie本質(zhì)上是一棵多叉樹。不過它和普通多叉樹的最大區(qū)別是樹的路徑并不代表權(quán)值而是代表字符序列節(jié)點本身沒有存儲所謂的“鍵值”它只記錄路徑終點的單詞標記。理解路徑即數(shù)據(jù)是理解Trie的關(guān)鍵一步。也有人會問為什么題目里把Trie叫做“前綴樹”因為它對前綴的存儲和檢索效率是最優(yōu)的。任何一個單詞它的任意前綴都對應(yīng)一條從根到某節(jié)點的路徑。反過來從根到某節(jié)點的路徑所代表的字符串一定是某個已有單詞的前綴。這個雙向映射關(guān)系讓前綴匹配變成了簡單的“路徑可達性判斷”這就是Trie名字的由來。3. 代碼逐行實現(xiàn)與算法流程拆解3.1 完整可運行的Java參考代碼現(xiàn)在我們把所有理論落到代碼層面。以下是我在LeetCode 208上直接提交通過的標準寫法包含關(guān)鍵注釋class TrieNode { // 固定26個字母的孩子指針數(shù)組初始都為null TrieNode[] children new TrieNode[26]; // 標記當前節(jié)點是否是一個單詞的結(jié)束 boolean isEnd; } class Trie { private TrieNode root; public Trie() { root new TrieNode(); } public void insert(String word) { TrieNode node root; for (char ch : word.toCharArray()) { int idx ch - a; if (node.children[idx] null) { node.children[idx] new TrieNode(); } node node.children[idx]; } node.isEnd true; } public boolean search(String word) { TrieNode node findNode(word); return node ! null node.isEnd; } public boolean startsWith(String prefix) { return findNode(prefix) ! null; } // 公共方法從根開始按字符移動返回字符串終點節(jié)點路徑不存在則返回null private TrieNode findNode(String s) { TrieNode node root; for (char ch : s.toCharArray()) { int idx ch - a; if (node.children[idx] null) { return null; } node node.children[idx]; } return node; } }這段代碼一共不到50行結(jié)構(gòu)非常清晰。我把findNode單獨抽出來就是為了讓search和startsWith共用路徑查找邏輯避免重復(fù)代碼。這也是一個讓面試官眼前一亮的細節(jié)——表明你在寫代碼時有意識地做了冗余消除。3.2 基于代碼走一遍實際用例用上面的代碼在內(nèi)存中模擬一下操作能直觀感受到Trie的運轉(zhuǎn)過程。假設(shè)依次執(zhí)行insert(apple)insert(app)search(app)search(appl)startsWith(app)。第一步插入apple。從根節(jié)點出發(fā)發(fā)現(xiàn)a下標位置為空新建節(jié)點并移過去pp、p、l、e同理依次新建。到達e節(jié)點后把isEnd置為true。此時樹中有一條鏈root - a - p - p - l - ee節(jié)點帶有isEndtrue標記。第二步插入app。從根走到a節(jié)點時發(fā)現(xiàn)已存在直接移過去p和p同理不新建節(jié)點。到達第二個p節(jié)點后把它的isEnd置為true。注意這個p節(jié)點之前是apple路徑的中間節(jié)點現(xiàn)在變成了一個完整單詞的終點。這就是isEnd字段的雙重身份它既可以標記終點也可以作為繼續(xù)向下的中間路徑。第三步search(app)。沿著路徑走到第二個p節(jié)點findNode返回該節(jié)點檢查isEnd發(fā)現(xiàn)為true因此返回true。第四步search(appl)。沿著路徑走到l節(jié)點isEnd為false返回false。這說明appl路徑存在但不是完整單詞符合預(yù)期。第五步startsWith(app)。findNode(app)返回的節(jié)點非空直接返回true不管這個節(jié)點是否被標記為單詞結(jié)尾。這個過程演示了Trie如何優(yōu)雅地處理單詞之間互為前綴的情況。如果用哈希表插入apple后你還得再插入app兩個字符串各自都存儲了一份app字符序列Trie則通過共享節(jié)點實現(xiàn)了存儲復(fù)用。3.3 動手實現(xiàn)時的三個編碼技巧這是一個很多刷題攻略不會細講的點但我想單獨拉出來說。技巧一選擇迭代而非遞歸實現(xiàn)。雖然遞歸在概念上更貼近樹結(jié)構(gòu)但Trie的遞歸需要額外傳入層級索引代碼里還要處理word.length()和idx的邊界關(guān)系容易搞混。相比之下迭代寫法中游標節(jié)點是唯一的可變狀態(tài)邏輯一目了然調(diào)試時只需要盯一個變量。技巧二利用c - a做索引映射而不是調(diào)用Character.getNumericValue之類的API。前者只做一次整型減法性能極佳而且可讀性足夠高。后者涉及方法調(diào)用和返回值判斷反而容易出現(xiàn)歧義讓讀者困惑。技巧三根節(jié)點初始化為空節(jié)點不代表任何字符。很多人剛開始學Trie會糾結(jié)“根節(jié)點對應(yīng)什么字符”其實根節(jié)點不代表任何字符它只是路徑的起點。插入時我們從第一個字符開始創(chuàng)建節(jié)點搜索時也從第一個字符開始移動指針。根節(jié)點本身只作為一個占位符存在它的isEnd默認為false。只有當插入空字符串時我們才直接把root的isEnd設(shè)為true——這個邊界情況雖然小眾LeetCode測試用例里確實會覆蓋。3.4 空字符串與重復(fù)插入的邊界場景空字符串和重復(fù)插入這兩個邊界值得單獨驗證一次?？兆址畧鼍皥?zhí)行insert()后word.toCharArray()產(chǎn)生的是空數(shù)組循環(huán)體一次都不執(zhí)行node始終是root最后把root.isEnd設(shè)為true。執(zhí)行search()時findNode同樣不進入循環(huán)直接返回root看到isEnd為true整個搜索返回true。這個邏輯完全通暢不用額外寫if判斷。如果實現(xiàn)時在insert的開頭就寫了if (word null || word.length() 0) return;之類的代碼反而會破壞這個合理行為。重復(fù)插入場景連續(xù)執(zhí)行兩次insert(app)。第一次會把最后一個p節(jié)點的isEnd置為true第二次再走一遍同樣的路徑節(jié)點都已在樹上所以不會新建任何節(jié)點最后重新把isEnd置為true。這一步是冪等的不影響后續(xù)搜索。內(nèi)置的List里有兩個優(yōu)化空間。一是可以在search接口增加一種“只查完整單詞”的分支比如我們后文會討論的LeetCode 211題就需要支持通配符匹配二是如果業(yè)務(wù)上需要統(tǒng)計某個單詞的插入次數(shù)可以在節(jié)點里加一個int類型的count字段而不是簡單的布爾isEnd。這些在第5節(jié)的變體題中會具體展示。4. 實操過程中的問題實錄與排查思路4.1 空指針異常排查一場典型的“漏判”我第一次在LeetCode上提交這段代碼時遇到了一種很典型的錯誤search的時候碰到null就返回false但有些測試用例期望返回true。仔細排查后發(fā)現(xiàn)問題出在findNode方法里。我當時寫的邏輯是private TrieNode findNode(String s) { TrieNode node root; for (char ch : s.toCharArray()) { TrieNode child node.children[ch - a]; if (child null) { return null; } node child; } return node; }這個邏輯看起來沒有問題但我在search方法里寫成了public boolean search(String word) { TrieNode node findNode(word); return node.isEnd; // 沒有判斷node非空 }一旦findNode返回null調(diào)用node.isEnd就會拋出NullPointerException。這種低級錯誤在緊張狀態(tài)下很容易犯特別是當你的findNode方法名看起來“很安全”、讓人下意識覺得返回值肯定不為null時。我的建議是把公共方法的返回類型做得像Optional那樣明確或者在調(diào)用前養(yǎng)成判空習慣。寫健壯代碼的第一步就是承認任何方法都可能返回null然后確保調(diào)用方處理這種情況。4.2 內(nèi)存占用過高的分析思路如果往Trie里塞了大量單詞Java堆內(nèi)存會顯著上漲。此時先把數(shù)據(jù)規(guī)模跑一遍大致算一下理論節(jié)點數(shù)再用jmap -histo或者Java VisualVM看實際對象數(shù)量。如果實際節(jié)點數(shù)遠超N*L的理論值多半是新增了意外的分支節(jié)點——比如插入了大量帶區(qū)別前綴的單詞或者數(shù)據(jù)結(jié)構(gòu)里出現(xiàn)了“節(jié)點的子節(jié)點數(shù)組沒有被復(fù)用”這種問題。排查時可以寫一個輔助方法統(tǒng)計整棵樹的節(jié)點總數(shù)public int countNodes() { return countNodes(root); } private int countNodes(TrieNode node) { if (node null) return 0; int count 1; for (TrieNode child : node.children) { count countNodes(child); } return count; }如果節(jié)點數(shù)不太合理就檢查是不是插入邏輯里創(chuàng)建了多余的根節(jié)點副本或者意外地插入了大量空白字符。這類排查本質(zhì)上是在幫你確認“代碼是否嚴格遵循了懶加載原則”。4.3 測試用例設(shè)計從簡單到刁鉆我強烈建議你在寫完Trie之后至少手動跑一遍以下測試序列先插入一個單詞再搜索這個單詞確認返回true。搜索一個不在樹中的單詞確認返回false。搜索一個前綴是樹里單詞、但不是完整單詞的情況確認返回false。先插入app再插入apple分別搜索兩個單詞確認都返回true。插入apple然后搜索app確認返回false因為app沒被標記為單詞。看startsWith(app)是否返回true。插入空字符串搜索空字符串確認返回true。重復(fù)插入同一單詞確認第二次插入后仍能正常搜索。搜索一個比所有已有單詞都長的字符串確認不報錯。這套用例覆蓋了Trie的核心邊界情況。如果你在本地跑完這套用例再去提交大概率一次通過。4.4 Python實現(xiàn)時的幾個小差異雖然本題在Java和C中都是經(jīng)典題型但Python的實現(xiàn)有幾個值得注意的點。首先是子節(jié)點存儲方式由于Python的列表不支持固定長度且類型安全的數(shù)組大部分題解會直接用dict存儲子節(jié)點——每個節(jié)點一個字典鍵是字符值是子節(jié)點。這樣在插入時只需要判斷char in node.children。另一個差異是Python沒有true char類型遍歷字符串時的字符本來就是一個小寫字母字符串直接當字典鍵使用不需要做c - a的算術(shù)運算。class TrieNode: def __init__(self): self.children {} self.is_end False class Trie: def __init__(self): self.root TrieNode() def insert(self, word: str) - None: node self.root for ch in word: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.is_end True def search(self, word: str) - bool: node self.root for ch in word: if ch not in node.children: return False node node.children[ch] return node.is_end def startsWith(self, prefix: str) - bool: node self.root for ch in prefix: if ch not in node.children: return False node node.children[ch] return True用字典的寫法有個好處將來要把字符集擴展到大寫字母、數(shù)字甚至漢字代碼一行都不用改。代價是HashMap查詢比數(shù)組索引稍慢。不過在LeetCode的數(shù)據(jù)規(guī)模下這個性能差異對AC毫無影響。刷題時你完全可以選擇自己最熟悉的語言來實現(xiàn)。5. 擴展從LeetCode 208到更廣闊的應(yīng)用場景5.1 高頻變形題與實戰(zhàn)題單LeetCode 208是很多進階題目的地基刷完這道題之后一定要趁熱打鐵把這些變體題都做一遍。LeetCode 211添加與搜索單詞。在Trie的基礎(chǔ)上增加通配符.的匹配能力。搜索時遇到.就必須遍歷當前節(jié)點的所有孩子節(jié)點這需要遞歸或顯式棧的幫助。這道題是對“Trie搜索遞歸化”的直接訓練。LeetCode 212單詞搜索II。在二維字符網(wǎng)格中找出現(xiàn)在字典里的所有單詞。常規(guī)做法是DFS加回溯但如果你先建一棵Trie搜索時用Trie做剪枝復(fù)雜度會大幅優(yōu)化。這道題結(jié)合了圖遍歷和前綴樹的優(yōu)勢屬于Trie最重要的實戰(zhàn)場景之一。LeetCode 648單詞替換。英文句子里的詞如果含有詞根就用詞根替代該詞。用Trie把所有詞根存起來然后對句子中每個單詞從左到右匹配前綴遇到最短的isEnd節(jié)點就替換。這題考察的是Trie在字符串處理流水線中的實際運用。LeetCode 745前綴和后綴搜索。這題比較綜合需要在前綴樹和后綴樹之間做組合查詢?nèi)绻麤]有牢固的Trie基礎(chǔ)會很難寫對。把這些題目都刷完你會自然形成“看到字符串匹配就先考慮Trie”的條件反射。5.2 Trie在真實工程中的應(yīng)用場景刷題只是手段理解Trie在真實世界中的位置才有長遠價值。三個最常見的場景搜索引擎的自動補全與輸入法聯(lián)想。用戶輸入前綴后系統(tǒng)需要快速返回候選詞列表。Trie天然支持前綴檢索再配合每個節(jié)點上的詞頻統(tǒng)計或者單獨維護的熱度堆就能實現(xiàn)穩(wěn)定高效的熱詞推薦。IP路由表的最長前綴匹配。計算機網(wǎng)絡(luò)里的路由表本質(zhì)上就是一棵二叉Trie樹匹配時尋找最長匹配前綴來決定數(shù)據(jù)包發(fā)送路徑。這里的字符集變成0和1節(jié)點存儲的是二進制位原理完全一致?；蛐蛄械谋葘εc存儲。DNA序列由A、T、C、G四種堿基組成可以把每條基因片段視作一個字符串公共片段在Trie中共享存儲既能壓縮存儲空間又能快速定位共同子串。這些場景都能反哺你對LeetCode 208的理解——為什么題目選擇26個小寫字母作為字符集為什么節(jié)點要標記isEnd為什么前綴匹配如此關(guān)鍵。把一道題放到更大的背景下看它就不再是一道孤立的題。5.3 刷題中的時間分配心得根據(jù)我對leetcode熱門100題和leetcode周賽的觀察Trie這類基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)題目通常是熱身題或鋪墊題。在實際比賽中它更多是作為更復(fù)雜題目的組成部分出現(xiàn)——比如周賽430里就可能有帶Trie剪枝的搜索題。我的建議是不要只在提交AC之后就急著看下一題先把這道題的實現(xiàn)細節(jié)吃透把變體題也做了形成一條完整的學習鏈。這種“以題帶點、以點帶面”的刷題節(jié)奏比盲目追求刷題數(shù)量要有效得多。倒不是我有多厲害而是我踩過盲刷的坑刷了300多道題遇到211還是想不起來用遞歸處理通配符。后來認真把Trie這一套變形題啃下來再遇到相關(guān)題型就不會卡殼了。6. 個人經(jīng)驗總結(jié)從“會寫”到“寫明白”Trie這道題的難點不在于代碼量而在于你有沒有把數(shù)據(jù)結(jié)構(gòu)的設(shè)計邏輯想透。很多人看題解一遍就會敲代碼但面試時被問到“為什么用數(shù)組而不用哈希表”“startsWith和search的區(qū)別除了isEnd還有什么”“插入重復(fù)單詞時樹會不會多出節(jié)點”就可能語塞。我特別建議在寫完代碼后自己給自己講一遍設(shè)計思路節(jié)點為什么是26個元素的數(shù)組插入為什么是邊移動邊判斷前綴匹配為什么不需要isEnd。能講清楚才算真的掌握了。這里再分享一個實用技巧LeetCode官方題解里有C和Java的參考實現(xiàn)它的代碼風格通常非常緊湊但未必最適合日常閱讀。我的做法是先用最清晰的寫法通過題目再用官方題解對比優(yōu)化空間。比如官方題解里的search和startsWith都直接寫了遍歷邏輯沒有抽取公共方法這是為了減少抽象層次。而我個人更推薦抽公共方法因為面對后續(xù)的211、212這類復(fù)雜的變形題時模塊化代碼更容易擴展。Trie是一塊敲門磚它能把“樹”的思維和“字符串”的特性緊密結(jié)合。把這道題徹底搞懂后面看AC自動機、雙數(shù)組Trie這些高級話題都會順暢很多。希望這篇實錄能幫你少走一些彎路。