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