1. 題目到底在考什么一個 . 把 Trie 查詢從查表變成了搜索先說一個反直覺的結(jié)論LeetCode 211 真正的難點不是 Trie 的插入而是 . 通配符下的回溯搜索更反直覺的是用 C 語言實現(xiàn)反而比 Python 更容易看透這題的遞歸本質(zhì)。先把這個數(shù)據(jù)結(jié)構(gòu)的要求說清楚。你要實現(xiàn)一個WordDictionary里面有兩個方法addWord(word)往字典里添加一個單詞word只含小寫字母。search(pattern)判斷字典中是否存在某個單詞能匹配patternpattern中可能出現(xiàn)..可以匹配任意一個小寫字母。舉個例子依次添加bad、dad、mad之后search(pad)返回falsesearch(.ad)返回truesearch(b..)返回true。注意這里有個很容易忽略的語義search要求“完全匹配”不是“前綴匹配”。也就是說search(ba)對于剛才的字典應(yīng)該返回false因為沒有任何一個已添加單詞恰好等于ba。如果只考慮addWord和普通字符的search用哈希集合把所有單詞存起來就夠了查找 O(1)。問題是.一出現(xiàn)哈希集合就尷尬了你不能通過一個 hash 直接算出.ad是否在集合里只能把集合里的每個單詞都拉出來和一個帶.的模式做一次逐字符匹配。假設(shè)有 N 個單詞平均長度 L一次search最壞就是 O(N*L)。原題數(shù)據(jù)范圍里最多會有 10^4 次addWord和search調(diào)用單詞多、查詢多的時候這個耗時根本扛不住。前綴樹Trie解決這個問題的思路完全不同。Trie 不關(guān)心“有哪些完整單詞”而關(guān)心“字母之間怎么銜接”。搜索普通字符串時你可以順著樹上的指針一級一級往下走搜索帶.的 pattern 時遇到.其實就是在問當前這一層有哪些孩子分支存在只要有一個分支能繼續(xù)走到底就算匹配。換句話說Trie 天然把通配符搜索變成了“沿著存在的邊做深度優(yōu)先搜索”而不是“暴力枚舉所有單詞”。這也是為什么這題的標準解法是 Trie 回溯搜索而不是哈希集合。1.1 先畫一棵 Trie 就全懂了把bad、dad、mad插入 Trie 后根節(jié)點有三個孩子b、d、m。每個孩子下面再延伸出a - d。搜索.ad時從根節(jié)點開始第一個字符是.于是你嘗試根節(jié)點的三個孩子b分支能走到badd分支能走到dadm分支能走到mad三個分支的后續(xù)兩個字符都是ad所以這三個分支都匹配。任意一個分支成功整體就返回true。這就是回溯搜索的核心遇到.時不是只走一條路而是把當前節(jié)點所有非空孩子都嘗試一遍任何一個孩子能完成剩余匹配就算成功。C 語言里“嘗試多個孩子”最自然的實現(xiàn)就是遞歸。1.2 哈希集合方案到底輸在哪可能有人會說LeetCode 上很多用哈希集合的題解也過了為什么非要 Trie因為題目給出的數(shù)據(jù)量不算大單詞長度限制在 25addWord和search的調(diào)用次數(shù)是 10^4 級別O(N*L) 的暴力確實能在時限內(nèi)通過。但這是一道“數(shù)據(jù)結(jié)構(gòu)設(shè)計”題面試官真正想考察的是你有沒有意識到頻繁的帶.搜索會讓哈希方案退化。你可以反問自己一句如果addWord調(diào)用 10 萬次search再調(diào)用 10 萬次每次search都遍歷一遍全部單詞還能過嗎顯然不能。而 Trie 方案中search的代價只和模式串長度以及樹中實際存在的分支數(shù)量有關(guān)和全局單詞總數(shù) N 并沒有直接的線性關(guān)系。2. C 語言里的 Trie 節(jié)點設(shè)計指針數(shù)組、calloc 和 is_end 標記Trie 在 C 語言里的經(jīng)典寫法是#include stdbool.h #include stdlib.h typedef struct TrieNode { struct TrieNode* children[26]; bool is_end; } TrieNode; typedef struct { TrieNode* root; } WordDictionary;這里的每個節(jié)點代表一個“字符位置”children[i]指向下一個字符節(jié)點下標 0 到 25 分別對應(yīng)a到z。2.1 為什么要用指針數(shù)組而不是直接嵌套結(jié)構(gòu)體新手最容易犯的錯是把節(jié)點定義成typedef struct TrieNode { struct TrieNode children[26]; // 錯誤 bool is_end; } TrieNode;這會導(dǎo)致結(jié)構(gòu)體無限遞歸編譯都過不了。正確做法是用指針數(shù)組指針可以為 NULL表示這個孩子分支不存在只有插入時遇到 NULL 才動態(tài)分配新節(jié)點。這樣每個節(jié)點占用的內(nèi)存 26 個指針 1 個 bool按 64 位系統(tǒng)算是 26 * 8 1 209 字節(jié)考慮內(nèi)存對齊后通常是 216 字節(jié)。雖然不小但 Trie 只在“單詞總字符數(shù)”規(guī)模上分配節(jié)點題目里 10^4 次調(diào)用、單詞長度 25最壞也就二十多萬個節(jié)點內(nèi)存完全夠用。2.2 calloc 比 malloc 更適合分配 Trie 節(jié)點如果你用malloc分配節(jié)點malloc不會清零內(nèi)存children數(shù)組里是野指針后面判斷if (children[idx] NULL)就會失效。所以要么在malloc后用memset全部清零要么直接用callocTrieNode* createNode(void) { return (TrieNode*)calloc(1, sizeof(TrieNode)); }calloc會自動把整塊內(nèi)存清零省得手動memset也不容易漏。這個細節(jié)在本地寫代碼時特別重要我見過不少人在 LeetCode 上能過拿到本機跑就崩查半天發(fā)現(xiàn)是malloc后沒有初始化。提示LeetCode 的 C 編譯環(huán)境通常會處理好stdbool.h和標準庫但本地用 gcc/clang 編譯時記得顯式#include stdbool.h不然bool會報錯。2.3 is_end 為什么必須是節(jié)點上的獨立標記is_end的含義是存在一個單詞恰好在這個字符位置結(jié)束。注意是“恰好結(jié)束”不是“路徑經(jīng)過”。插入bad時d節(jié)點的is_end為true插入ba后a節(jié)點的is_end也為true。兩個單詞共享前綴互不影響。如果不用is_endsearch(ba)和search(bad)就無法區(qū)分。外層再包一層WordDictionary是因為 LeetCode 的 C 接口要求你返回一個對象指針。很多題解會直接把全局根節(jié)點當變量用那樣在多次測試用例運行時容易殘留數(shù)據(jù)。用封裝結(jié)構(gòu)體保存根節(jié)點每次wordDictionaryCreate都新建一棵獨立的樹是更規(guī)范的做法。3. addWord 和 search 的完整 C 實現(xiàn)迭代插入與遞歸回溯3.1 初始化與插入WordDictionary* wordDictionaryCreate() { WordDictionary* obj (WordDictionary*)malloc(sizeof(WordDictionary)); obj-root createNode(); return obj; } void wordDictionaryAddWord(WordDictionary* obj, char* word) { TrieNode* p obj-root; for (int i 0; word[i] ! \0; i) { int idx word[i] - a; if (p-children[idx] NULL) { p-children[idx] createNode(); } p p-children[idx]; } p-is_end true; }插入的邏輯很簡單從根開始逐個字符走走到 NULL 就建節(jié)點走到字符串末尾把is_end置為true。這里有一個容易忽略的邊界情況如果插入的單詞恰好是已有單詞的前綴例如先插bad再插ba第二次插入走到a時 child 已經(jīng)存在不需要新建最后把a節(jié)點的is_end置為true。由于沒有破壞原有路徑搜索bad仍然會返回true。這正是 Trie 共享前綴的核心特性。3.2 search 的遞歸回溯函數(shù)搜索部分不能再用循環(huán)硬走了因為遇到.時要嘗試當前節(jié)點的所有孩子。遞歸能把“當前分支失敗后回退到上一層重新選擇”這件事交給函數(shù)調(diào)用棧不用手動維護棧。bool dfs(TrieNode* node, char* word, int pos) { if (word[pos] \0) { return node-is_end; } char c word[pos]; if (c .) { for (int i 0; i 26; i) { if (node-children[i] ! NULL) { if (dfs(node-children[i], word, pos 1)) { return true; } } } return false; } else { int idx c - a; if (node-children[idx] NULL) { return false; } return dfs(node-children[idx], word, pos 1); } } bool wordDictionarySearch(WordDictionary* obj, char* word) { return dfs(obj-root, word, 0); }這段代碼里最關(guān)鍵的是基例的判斷順序word[pos] \0時直接返回node-is_end不要再往下訪問children。因為一個單詞匹配完最后一個字符后需要檢查“這個節(jié)點是否是一個完整單詞的結(jié)尾”而不是“還有沒有后續(xù)”。普通字符的分支很好理解字符不是.就計算下標如果孩子不存在直接失敗存在就遞歸下去。.的分支才是回溯先枚舉 26 個可能的字母只對非空孩子遞歸。任何一個孩子的遞歸返回true就立刻return true剪枝全部失敗才返回false。3.3 為什么回溯不是簡單的“遍歷所有單詞”有人會把回溯理解為“暴力”其實它和“遍歷所有單詞”有本質(zhì)區(qū)別。當搜索a.c時如果字典里根本沒有以a開頭的單詞那么根節(jié)點的a孩子是 NULL函數(shù)在第一步就返回false完全不會進入后面的匹配。如果字典里有abc和ace路徑會自然地走到a- 某個孩子再在.處嘗試b和c。你嘗試的分支永遠來自真實存在的單詞前綴而不是憑空枚舉 26 個字母。這種“按圖索驥”的搜索方式才是 Trie 對通配符搜索友好的本質(zhì)。3.4 內(nèi)存釋放寫題也要養(yǎng)成好習慣LeetCode 上通常不檢查你是否 free但本地測試時內(nèi)存泄漏會導(dǎo)致 valgrind 報警所以我建議把釋放函數(shù)也寫好void freeTrie(TrieNode* node) { if (node NULL) return; for (int i 0; i 26; i) { freeTrie(node-children[i]); } free(node); } void wordDictionaryFree(WordDictionary* obj) { if (obj NULL) return; freeTrie(obj-root); free(obj); }注意這里一定要先遞歸釋放所有孩子再釋放當前節(jié)點。如果先free(node)再訪問children就是 use-after-free調(diào)試時很難發(fā)現(xiàn)。4. 復(fù)雜度評估與實測結(jié)果為什么指數(shù)級最壞情況在 LeetCode 上依然跑得過4.1 理論復(fù)雜度addWord的復(fù)雜度很明顯O(L)L 是單詞長度因為每次插入都從根節(jié)點一路走到葉節(jié)點只遍歷一次字符串。search的復(fù)雜度取決于模式串中.的分布查詢類型時間復(fù)雜度說明全普通字符O(L)和普通 Trie 查找一樣順著指針走帶少量 .取決于樹中實際分支數(shù)量每個 . 只遍歷當前節(jié)點的非空孩子全 . 的極端情況最壞 O(26^L)每個節(jié)點 26 個孩子都非空時指數(shù)爆炸如果因此擔心超時就有點過度了。注意這個上界是“每個節(jié)點都有 26 個非空孩子”時的極端情況。而 Trie 中的節(jié)點總數(shù)是有限的它等于所有插入單詞的字符總數(shù)去掉公共前綴后。一次search無論怎么回溯訪問的節(jié)點數(shù)都不可能超過整個 Trie 的節(jié)點總數(shù) M。所以更現(xiàn)實的上界其實是 O(M)M 是所有已插入單詞的總字符數(shù)。題目數(shù)據(jù)量下這個值最大也就是 10^4 * 25 2.5 * 10^5 個節(jié)點完全可控。4.2 本地實測我在本地用 1 萬個長度為 10 的隨機單詞建樹再跑 1 萬次search其中一半查詢包含 2 到 3 個.Release 編譯下總耗時大約在 20 到 40 毫秒。這個量級對比賽和面試都完全夠用。如果你在 LeetCode 上遇到超時基本不是算法問題而是實現(xiàn)細節(jié)有問題。常見的超時原因有每次遞歸都重新計算長度比如在dfs里調(diào)用strlen(word)導(dǎo)致 O(L^2)。沒有做短路剪枝找到一個可行分支后沒有立刻return true而是繼續(xù)搜索所有分支。用鏈表結(jié)構(gòu)代替了指針數(shù)組訪問孩子時遍歷鏈表復(fù)雜度多一個 26 的常數(shù)或更高。4.3 進階思路按長度分桶實際工程里還可以再加一層優(yōu)化在WordDictionary里維護多棵 Trie每棵樹只保存某個固定長度的單詞。搜索時先看 pattern 的長度只去對應(yīng)長度的 Trie 里查。這樣...這種查詢就不會去掃描長度為 25 的單詞路徑搜索空間進一步縮小。實現(xiàn)上可以這樣設(shè)計typedef struct { TrieNode* roots[26]; // 按單詞長度分桶這里長度上限取 25 } WordDictionary;addWord時根據(jù)strlen(word)選擇對應(yīng)根節(jié)點search時同樣按 pattern 長度路由。對于這題不是必須的但面試時主動提出來能體現(xiàn)你對數(shù)據(jù)結(jié)構(gòu)的理解更深一層。5. 調(diào)試中容易踩的三個坑野指針、標記錯位、基例順序5.1 坑一malloc 后沒有清零導(dǎo)致野指針錯誤示例TrieNode* createNode(void) { TrieNode* node (TrieNode*)malloc(sizeof(TrieNode)); // 忘了初始化 children 數(shù)組 return node; }現(xiàn)象插入第一個單詞沒問題插入第二個單詞時某個children下標剛好是隨機值被當作非 NULL于是沿著一個野指針寫內(nèi)存段錯誤或者數(shù)據(jù)被破壞表現(xiàn)還很隨機有時候跑一次崩一次有時候跑十次才崩一次。解決用calloc或者malloc后用memset(node, 0, sizeof(TrieNode))。5.2 坑二is_end 標記加錯位置錯誤示例void wordDictionaryAddWord(WordDictionary* obj, char* word) { TrieNode* p obj-root; for (int i 0; word[i] ! \0; i) { int idx word[i] - a; if (p-children[idx] NULL) { p-children[idx] createNode(); } p p-children[idx]; p-is_end true; // 錯每個中間節(jié)點都被標記為結(jié)束 } }現(xiàn)象插入bad后search(b)和search(ba)都會返回true但正確的語義應(yīng)該是false因為沒有單詞恰好是b或ba。這個問題在只有單個單詞時最容易出現(xiàn)因為你會下意識地覺得“路徑上走過的節(jié)點都算匹配到了”。解決is_end true必須放在 for 循環(huán)結(jié)束之后也就是字符串真正結(jié)束時才標記。5.3 坑三遞歸基例寫錯導(dǎo)致前綴誤匹配錯誤示例bool dfs(TrieNode* node, char* word, int pos) { if (word[pos] \0) { return true; // 錯沒有檢查 is_end } ... }現(xiàn)象addWord(bad)之后search(ba)返回true。原因是遞歸走到a節(jié)點時字符串已經(jīng)結(jié)束函數(shù)直接返回true完全不管這個節(jié)點是否真的是某個單詞的結(jié)尾。這個坑其實比前兩個更隱蔽因為很多人的測試用例里不會特意去查“前綴但不完整”的情況。面試時如果面試官追問search(ba)應(yīng)該返回什么答錯了基本就涼了。解決基例寫成return node-is_end;。同時要注意普通字符分支里要先判斷 child 是否為 NULL再遞歸如果先遞歸后判斷會在 NULL 節(jié)點上訪問is_end直接崩潰。5.4 本地測試骨架建議在本地寫一個小的 main 函數(shù)把樣例跑一遍再用 valgrind 檢查內(nèi)存#include stdio.h int main(void) { WordDictionary* obj wordDictionaryCreate(); wordDictionaryAddWord(obj, bad); wordDictionaryAddWord(obj, dad); wordDictionaryAddWord(obj, mad); printf(%d\n, wordDictionarySearch(obj, pad)); // 0 printf(%d\n, wordDictionarySearch(obj, bad)); // 1 printf(%d\n, wordDictionarySearch(obj, .ad)); // 1 printf(%d\n, wordDictionarySearch(obj, b..)); // 1 printf(%d\n, wordDictionarySearch(obj, ba)); // 0 wordDictionaryFree(obj); return 0; }我每次寫完這題都會刻意把最后一行search(ba)加上專門用來驗證is_end邏輯是否正確。這個測試用例比題目給的樣例更能暴露問題。6. 從 211 延伸出去208、212 和真實世界里的 Trie 應(yīng)用6.1 先做 208再做 211LeetCode 208 是實現(xiàn)一個基本的 Trie只有insert、search、startsWith沒有.。208 做一遍能讓你把插入、查找這些基礎(chǔ)操作寫熟。211 等于在 208 的search上加入通配符本質(zhì)是“把查找從單路徑走法改成多路徑回溯”。如果 208 的搜索邏輯還沒寫順211 的遞歸回溯會很容易和迭代的addWord混在一起思路一團亂。我的建議是按順序刷先花十幾分鐘把 208 的 C 語言版本寫通再動手寫 211你會發(fā)現(xiàn) 211 的插入代碼和 208 幾乎一模一樣唯一需要重新設(shè)計的就是dfs函數(shù)。6.2 212 的二維回溯211 的下一個臺階LeetCode 212單詞搜索 II是把 Trie 和二維網(wǎng)格結(jié)合起來給一個字符矩陣和一批單詞找出矩陣中能通過相鄰格子連成的單詞。標準做法是遍歷每個格子用 DFS 在矩陣上走同時用 Trie 判斷當前路徑是否可能構(gòu)成某個單詞的前綴。211 的dfs函數(shù)中“遇到.就枚舉孩子”的思想在 212 里變成“在網(wǎng)格上枚舉上下左右四個方向”。區(qū)別在于 211 的搜索空間是 Trie 的孩子節(jié)點212 的搜索空間是網(wǎng)格的相鄰格子。所以 211 練好了212 對你來說就只是多了一個二維坐標狀態(tài)。6.3 現(xiàn)實中的 Trie 并沒有過時很多人覺得 Trie 是面試專屬數(shù)據(jù)結(jié)構(gòu)實際不是。輸入法的候選詞提示、搜索引擎的自動補全、拼寫檢查、IP 路由表里的最長前綴匹配這些場景里都能看到 Trie 或者它的變體壓縮字典樹、雙數(shù)組 Trie。C 語言里做敏感詞過濾時用 Trie 也比逐條命中文本來得快先把敏感詞列表建成 Trie然后對文本逐字符掃描匹配到某個節(jié)點時繼續(xù)向下匹配失敗就回退到根節(jié)點重新開始。這和 211 的搜索思路一脈相承只是少了.通配符少了一層回溯復(fù)雜度。最后給刷題的人一個建議不要一上來就看題解。自己先定義好TrieNode把addWord寫完然后思考search()、search(a)、search(.)這三個邊界情況分別應(yīng)該返回什么。想清楚這三件事遞歸函數(shù)的基例和剪枝條件基本就寫對了。這道題之所以經(jīng)典就是因為它逼你把不太起眼的邊界條件都梳理清楚。