作者：labuladong

公眾號(hào)：labuladong

讀完本文，可以去力扣解決如下題目：

208. 實(shí)現(xiàn) Trie (前綴樹(shù))（Medium）

1804. 實(shí)現(xiàn) Trie （前綴樹(shù)） II（Medium）

648. 單詞替換（Medium）

211. 添加與搜索單詞（Medium）

677. 鍵值映射（Medium）

Trie 樹(shù)又叫字典樹(shù)、前綴樹(shù)、單詞查找樹(shù)，是一種二叉樹(shù)衍生出來(lái)的高級(jí)數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用場(chǎng)景是處理字符串前綴相關(guān)的操作。

后臺(tái)有挺多讀者說(shuō)今年的面試筆試題涉及到這種數(shù)據(jù)結(jié)構(gòu)了，所以請(qǐng)我講一講。

幾年前我在《算法 4》第一次學(xué)到這種數(shù)據(jù)結(jié)構(gòu)，不過(guò)個(gè)人認(rèn)為講解不是特別通俗易懂，所以本文按照我的邏輯幫大家重新梳理一遍 Trie 樹(shù)的原理，并基于《算法 4》的代碼實(shí)現(xiàn)一套更通用易懂的代碼模板，用于處理力扣上一系列字符串前綴問(wèn)題。

閱讀本文之前希望你讀過(guò)我舊文講過(guò)的回溯算法代碼模板和手把手刷二叉樹(shù)（總結(jié)篇）。

本文主要分三部分：

1、講解 Trie 樹(shù)的工作原理。

2、給出一套TrieMap和TrieSet的代碼模板，實(shí)現(xiàn)幾個(gè)常用 API。

3、實(shí)踐環(huán)節(jié)，直接套代碼模板秒殺 5 道算法題。本來(lái)可以秒殺七八道題，篇幅考慮，剩下的我集成到刷題插件中。

關(guān)于Map和Set，是兩個(gè)抽象數(shù)據(jù)結(jié)構(gòu)（接口），Map存儲(chǔ)一個(gè)鍵值對(duì)集合，其中鍵不重復(fù)，Set存儲(chǔ)一個(gè)不重復(fù)的元素集合。

常見(jiàn)的Map和Set的底層實(shí)現(xiàn)原理有哈希表和二叉搜索樹(shù)兩種，比如 Java 的 HashMap/HashSet 和 C++ 的 unorderd_map/unordered_set 底層就是用哈希表實(shí)現(xiàn)，而 Java 的 TreeMap/TreeSet 和 C++ 的 map/set 底層使用紅黑樹(shù)這種自平衡 BST 實(shí)現(xiàn)的。

而本文實(shí)現(xiàn)的 TrieSet/TrieMap 底層則用 Trie 樹(shù)這種結(jié)構(gòu)來(lái)實(shí)現(xiàn)。

了解數(shù)據(jù)結(jié)構(gòu)的讀者應(yīng)該知道，本質(zhì)上Set可以視為一種特殊的Map，Set其實(shí)就是Map中的鍵。

所以本文先實(shí)現(xiàn)TrieMap，然后在TrieMap的基礎(chǔ)上封裝出TrieSet。

PS：為了模板通用性的考慮，后文會(huì)用到 Java 的泛型，也就是用尖括號(hào)<>指定的類(lèi)型變量。這些類(lèi)型變量的作用是指定我們實(shí)現(xiàn)的容器中存儲(chǔ)的數(shù)據(jù)類(lèi)型，類(lèi)比 Java 標(biāo)準(zhǔn)庫(kù)的那些容器的用法應(yīng)該不難理解。

前文學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的框架思維說(shuō)過(guò)，各種亂七八糟的結(jié)構(gòu)都是為了在「特定場(chǎng)景」下盡可能高效地進(jìn)行增刪查改。

你比如HashMap的優(yōu)勢(shì)是能夠在 O(1) 時(shí)間通過(guò)鍵查找對(duì)應(yīng)的值，但要求鍵的類(lèi)型K必須是「可哈希」的；而TreeMap的特點(diǎn)是方便根據(jù)鍵的大小進(jìn)行操作，但要求鍵的類(lèi)型K必須是「可比較」的。

本文要實(shí)現(xiàn)的TrieMap也是類(lèi)似的，由于 Trie 樹(shù)原理，我們要求TrieMap的鍵必須是字符串類(lèi)型，值的類(lèi)型V可以隨意。

接下來(lái)我們了解一下 Trie 樹(shù)的原理，看看為什么這種數(shù)據(jù)結(jié)構(gòu)能夠高效操作字符串。

Trie 樹(shù)原理

Trie 樹(shù)本質(zhì)上就是一棵從二叉樹(shù)衍生出來(lái)的多叉樹(shù)。

二叉樹(shù)節(jié)點(diǎn)的代碼實(shí)現(xiàn)是這樣：

/*基本的二叉樹(shù)節(jié)點(diǎn)*/
classTreeNode{
intval;
TreeNodeleft,right;
}

其中left, right存儲(chǔ)左右子節(jié)點(diǎn)的指針，所以二叉樹(shù)的結(jié)構(gòu)是這樣：

多叉樹(shù)節(jié)點(diǎn)的代碼實(shí)現(xiàn)是這樣：

/*基本的多叉樹(shù)節(jié)點(diǎn)*/
classTreeNode{
intval;
TreeNode[]children;
}

其中children數(shù)組中存儲(chǔ)指向孩子節(jié)點(diǎn)的指針，所以多叉樹(shù)的結(jié)構(gòu)是這樣：

而TrieMap中的樹(shù)節(jié)點(diǎn)TrieNode的代碼實(shí)現(xiàn)是這樣：

/*Trie樹(shù)節(jié)點(diǎn)實(shí)現(xiàn)*/
classTrieNode<V>{
Vval=null;
TrieNode[]children=newTrieNode[256];
}

這個(gè)val字段存儲(chǔ)鍵對(duì)應(yīng)的值，children數(shù)組存儲(chǔ)指向子節(jié)點(diǎn)的指針。

但是和之前的普通多叉樹(shù)節(jié)點(diǎn)不同，TrieNode中children數(shù)組的索引是有意義的，代表鍵中的一個(gè)字符。

比如說(shuō)children[97]如果非空，說(shuō)明這里存儲(chǔ)了一個(gè)字符'a'，因?yàn)?code style="margin-right:2px;margin-left:2px;padding:2px 4px;font-size:inherit;line-height:inherit;color:rgb(233,105,0);background:rgb(248,248,248);">'a'的 ASCII 碼為 97。

我們的模板只考慮處理 ASCII 字符，所以children數(shù)組的大小設(shè)置為 256。不過(guò)這個(gè)可以根據(jù)具體問(wèn)題修改，比如改成更小的數(shù)組或者HashMap都是一樣的效果。

有了以上鋪墊，Trie 樹(shù)的結(jié)構(gòu)是這樣的：

一個(gè)節(jié)點(diǎn)有 256 個(gè)子節(jié)點(diǎn)指針，但大多數(shù)時(shí)候都是空的，可以省略掉不畫(huà)，所以一般你看到的 Trie 樹(shù)長(zhǎng)這樣：

這是在TrieMap中插入一些鍵值對(duì)后的樣子，白色節(jié)點(diǎn)代表val字段為空，橙色節(jié)點(diǎn)代表val字段非空。

這里要特別注意，TrieNode節(jié)點(diǎn)本身只存儲(chǔ)val字段，并沒(méi)有一個(gè)字段來(lái)存儲(chǔ)字符，字符是通過(guò)子節(jié)點(diǎn)在父節(jié)點(diǎn)的children數(shù)組中的索引確定的。

形象理解就是，Trie 樹(shù)用「樹(shù)枝」存儲(chǔ)字符串（鍵），用「節(jié)點(diǎn)」存儲(chǔ)字符串（鍵）對(duì)應(yīng)的數(shù)據(jù)（值）。所以我在圖中把字符標(biāo)在樹(shù)枝，鍵對(duì)應(yīng)的值val標(biāo)在節(jié)點(diǎn)上：

明白這一點(diǎn)很重要，有助于之后你理解代碼實(shí)現(xiàn)。

PS：《算法 4》以及網(wǎng)上講 Trie 樹(shù)的很多文章中都是把字符標(biāo)在節(jié)點(diǎn)上，我認(rèn)為這樣很容易讓初學(xué)者產(chǎn)生誤解，所以建議大家按照我的這種理解來(lái)記憶 Trie 樹(shù)結(jié)構(gòu)。

現(xiàn)在你應(yīng)該知道為啥 Trie 樹(shù)也叫前綴樹(shù)了，因?yàn)槠渲械淖址蚕砬熬Y，相同前綴的字符串集中在 Trie 樹(shù)中的一個(gè)子樹(shù)上，給字符串的處理帶來(lái)很大的便利。

TrieMap/TrieSet API 及實(shí)現(xiàn)

首先我們看一下本文實(shí)現(xiàn)的TrieMap的 API，為了舉例 API 的功能，假設(shè) TrieMap 中已經(jīng)存儲(chǔ)了如下鍵值對(duì)：

//底層用Trie樹(shù)實(shí)現(xiàn)的鍵值映射
//鍵為String類(lèi)型，值為類(lèi)型VclassTrieMap<V>{

/*****增/改*****/

//在Map中添加key
publicvoidput(Stringkey,Vval);

/*****刪*****/

//刪除鍵key以及對(duì)應(yīng)的值
publicvoidremove(Stringkey);

/*****查*****/

//搜索key對(duì)應(yīng)的值，不存在則返回null
//get("the")->4
//get("tha")->null
publicVget(Stringkey);

//判斷key是否存在在Map中
//containsKey("tea")->false
//containsKey("team")->true
publicbooleancontainsKey(Stringkey);

//在Map的所有鍵中搜索query的最短前綴
//shortestPrefixOf("themxyz")->"the"
publicStringshortestPrefixOf(Stringquery);

//在Map的所有鍵中搜索query的最長(zhǎng)前綴
//longestPrefixOf("themxyz")->"them"
publicStringlongestPrefixOf(Stringquery);

//搜索所有前綴為prefix的鍵
//keysWithPrefix("th")->["that","the","them"]
publicListkeysWithPrefix(Stringprefix);

//判斷是和否存在前綴為prefix的鍵
//hasKeyWithPrefix("tha")->true
//hasKeyWithPrefix("apple")->false
publicbooleanhasKeyWithPrefix(Stringprefix);

//通配符.匹配任意字符，搜索所有匹配的鍵
//keysWithPattern("t.a.")->["team","that"]
publicListkeysWithPattern(Stringpattern);

//通配符.匹配任意字符，判斷是否存在匹配的鍵
//hasKeyWithPattern(".ip")->true
//hasKeyWithPattern(".i")->false
publicbooleanhasKeyWithPattern(Stringpattern);

//返回Map中鍵值對(duì)的數(shù)量
publicintsize();
}

至于TrieSet的 API 大同小異，所以這里不重復(fù)列舉，后文直接給出實(shí)現(xiàn)。

接下來(lái)是重頭戲，我們一個(gè)一個(gè)實(shí)現(xiàn)TrieMap的上述 API 函數(shù)。

首先，TrieMap類(lèi)中一定需要記錄 Trie 的根節(jié)點(diǎn)root，以及 Trie 樹(shù)中的所有節(jié)點(diǎn)數(shù)量用于實(shí)現(xiàn)size()方法：

classTrieMap<V>{
//ASCII碼個(gè)數(shù)
privatestaticfinalintR=256;
//當(dāng)前存在Map中的鍵值對(duì)個(gè)數(shù)
privateintsize=0;

privatestaticclassTrieNode<V>{
Vval=null;
TrieNode[]children=newTrieNode[R];
}

//Trie樹(shù)的根節(jié)點(diǎn)
privateTrieNoderoot=null;

/*其他API的實(shí)現(xiàn)...*/

publicintsize(){
returnsize;
}
}

另外，我們?cè)賹?shí)現(xiàn)一個(gè)工具函數(shù)getNode：

//從節(jié)點(diǎn)node開(kāi)始搜索key，如果存在返回對(duì)應(yīng)節(jié)點(diǎn)，否則返回null
privateTrieNodegetNode(TrieNodenode,Stringkey){
TrieNodep=node;
//從節(jié)點(diǎn)node開(kāi)始搜索key
for(inti=0;iif(p==null){
//無(wú)法向下搜索
returnnull;
}
//向下搜索
charc=key.charAt(i);
p=p.children[c];
}
returnp;
}

有了這個(gè)getNode函數(shù)，就能實(shí)現(xiàn)containsKey方法和get方法了：

//搜索key對(duì)應(yīng)的值，不存在則返回null
publicVget(Stringkey){
//從root開(kāi)始搜索key
TrieNodex=getNode(root,key);
if(x==null||x.val==null){
//x為空或x的val字段為空都說(shuō)明key沒(méi)有對(duì)應(yīng)的值
returnnull;
}
returnx.val;
}

//判斷key是否存在在Map中
publicbooleancontainsKey(Stringkey){
returnget(key)!=null;
}

這里需要注意，就算getNode(key)的返回值x非空，也只能說(shuō)字符串key是一個(gè)「前綴」；除非x.val同時(shí)非空，才能判斷鍵key存在。

不過(guò)，這個(gè)特性恰好能夠幫我們實(shí)現(xiàn)hasKeyWithPrefix方法：

//判斷是和否存在前綴為prefix的鍵
publicbooleanhasKeyWithPrefix(Stringprefix){
//只要能找到 prefix 對(duì)應(yīng)的節(jié)點(diǎn)，就是存在前綴
returngetNode(root,prefix)!=null;
}

類(lèi)似getNode方法的邏輯，我們可以實(shí)現(xiàn)shortestPrefixOf方法，只要在第一次遇到存有val的節(jié)點(diǎn)的時(shí)候返回就行了：

//在所有鍵中尋找query的最短前綴
publicStringshortestPrefixOf(Stringquery){
TrieNodep=root;
//從節(jié)點(diǎn)node開(kāi)始搜索key
for(inti=0;iif(p==null){
//無(wú)法向下搜索
return"";
}
if(p.val!=null){
//找到一個(gè)鍵是query的前綴
returnquery.substring(0,i);
}
//向下搜索
charc=query.charAt(i);
p=p.children[c];
}

if(p!=null&&p.val!=null){
//如果query本身就是一個(gè)鍵
returnquery;
}
return"";
}

這里需要注意的是 for 循環(huán)結(jié)束之后我們還需要額外檢查一下。

因?yàn)橹罢f(shuō)了 Trie 樹(shù)中「樹(shù)枝」存儲(chǔ)字符串，「節(jié)點(diǎn)」存儲(chǔ)字符串對(duì)應(yīng)的值，for 循環(huán)相當(dāng)于只遍歷了「樹(shù)枝」，但漏掉了最后一個(gè)「節(jié)點(diǎn)」，即query本身就是TrieMap中的一個(gè)鍵的情況。

如果你理解了shortestPrefixOf的實(shí)現(xiàn)，那么longestPrefixOf也是非常類(lèi)似的：

//在所有鍵中尋找query的最長(zhǎng)前綴
publicStringlongestPrefixOf(Stringquery){
TrieNodep=root;
//記錄前綴的最大長(zhǎng)度
intmax_len=0;

//從節(jié)點(diǎn)node開(kāi)始搜索key
for(inti=0;iif(p==null){
//無(wú)法向下搜索
break;
}
if(p.val!=null){
//找到一個(gè)鍵是query的前綴，更新前綴的最大長(zhǎng)度
max_len=i;
}
//向下搜索
charc=query.charAt(i);
p=p.children[c];
}

if(p!=null&&p.val!=null){
//如果query本身就是一個(gè)鍵
returnquery;
}
returnquery.substring(0,max_len);
}

每次遇到p.val非空的時(shí)候說(shuō)明找到一個(gè)鍵，但是我們不急著返回，而是更新max_len變量，記錄最長(zhǎng)前綴的長(zhǎng)度。

同樣的，在 for 循環(huán)結(jié)束時(shí)還是要特殊判斷一下，處理query本身就是鍵的情況。

接下來(lái)，我們來(lái)實(shí)現(xiàn)keysWithPrefix方法，得到所有前綴為prefix的鍵。

看過(guò)前文手把手刷二叉樹(shù)（總結(jié)篇）的讀者應(yīng)該可以想到，先利用getNode函數(shù)在 Trie 樹(shù)中找到prefix對(duì)應(yīng)的節(jié)點(diǎn)x，然施展多叉樹(shù)的遍歷算法，遍歷以x為根的這棵 Trie 樹(shù)，找到所有鍵值對(duì)：

代碼實(shí)現(xiàn)如下：

//搜索前綴為prefix的所有鍵
publicListkeysWithPrefix(Stringprefix){
Listres=newLinkedList<>();
//找到匹配prefix在Trie樹(shù)中的那個(gè)節(jié)點(diǎn)
TrieNodex=getNode(root,prefix);
if(x==null){
returnres;
}
//DFS遍歷以x為根的這棵Trie樹(shù)
traverse(x,newStringBuilder(prefix),res);
returnres;
}

//遍歷以node節(jié)點(diǎn)為根的Trie樹(shù)，找到所有鍵
privatevoidtraverse(TrieNodenode,StringBuilderpath,Listres){
if(node==null){
//到達(dá)Trie樹(shù)底部葉子結(jié)點(diǎn)
return;
}

if(node.val!=null){
//找到一個(gè)key，添加到結(jié)果列表中
res.add(path.toString());
}

//回溯算法遍歷框架
for(charc=0;c//做選擇
path.append(c);
traverse(node.children[c],path,res);
//撤銷(xiāo)選擇
path.deleteCharAt(path.length()-1);
}
}

這段代碼中traverse函數(shù)你可能看起來(lái)特別熟悉，就是回溯算法核心套路中講的回溯算法代碼框架。

關(guān)于回溯算法框架和標(biāo)準(zhǔn)多叉樹(shù)框架的區(qū)別我在圖論算法基礎(chǔ)中探討過(guò)，關(guān)鍵在于遍歷「節(jié)點(diǎn)」和遍歷「樹(shù)枝」的區(qū)別。由于 Trie 樹(shù)將字符存儲(chǔ)在「樹(shù)枝」上，traverse函數(shù)是在遍歷樹(shù)枝上的字符，所以采用的是回溯算法框架。

另外，再注意一下這段邏輯：

//回溯算法遍歷框架
for(charc=0;c//做選擇
path.append(c);
traverse(node.children[c],path,res);
//撤銷(xiāo)選擇
path.deleteCharAt(path.length()-1);
}

回顧一下我們 Trie 樹(shù)的圖：

你是否會(huì)有疑問(wèn)：代碼中 for 循環(huán)會(huì)執(zhí)行 256 次，但是圖中的一個(gè)節(jié)點(diǎn)只有幾個(gè)子節(jié)點(diǎn)，也就是說(shuō)每個(gè)節(jié)點(diǎn)的children數(shù)組中大部分都是空指針，這不會(huì)有問(wèn)題嗎？

是不是應(yīng)該把代碼改成這樣：

//回溯算法遍歷框架
for(charc=0;c//做選擇
path.append(c);
if(node.children[c]!=null){
traverse(node.children[c],path,res);
}
//撤銷(xiāo)選擇
path.deleteCharAt(path.length()-1);
}

答案是，改不改都行，這兩種寫(xiě)法從邏輯上講完全相同，因?yàn)?code style="margin-right:2px;margin-left:2px;padding:2px 4px;font-size:inherit;line-height:inherit;color:rgb(233,105,0);background:rgb(248,248,248);">traverse函數(shù)開(kāi)始的時(shí)候如果發(fā)現(xiàn)node == null也會(huì)直接返回。

我為了保持框架的一致性，就沒(méi)有在 for 循環(huán)中判斷子節(jié)點(diǎn)是否為空，而是依賴遞歸函數(shù)的 base case。當(dāng)然你完全可以按照自己的喜好來(lái)實(shí)現(xiàn)。

下面來(lái)實(shí)現(xiàn)keysWithPattern方法，使用通配符來(lái)匹配多個(gè)鍵，其關(guān)鍵就在于通配符.可以匹配所有字符。

在代碼實(shí)現(xiàn)上，用path變量記錄匹配鍵的路徑，遇到通配符時(shí)使用類(lèi)似回溯算法的框架就行了：

//通配符.匹配任意字符
publicListkeysWithPattern(Stringpattern){
Listres=newLinkedList<>();
traverse(root,newStringBuilder(),pattern,0,res);
returnres;
}

//遍歷函數(shù)，嘗試在「以node為根的Trie樹(shù)中」匹配pattern[i..]
privatevoidtraverse(TrieNodenode,StringBuilderpath,Stringpattern,inti,Listres){
if(node==null){
//樹(shù)枝不存在，即匹配失敗
return;
}
if(i==pattern.length()){
//pattern匹配完成
if(node.val!=null){
//如果這個(gè)節(jié)點(diǎn)存儲(chǔ)著val，則找到一個(gè)匹配的鍵
res.add(path.toString());
}
return;
}
charc=pattern.charAt(i);
if(c=='.'){
//pattern[i]是通配符，可以變化成任意字符
//多叉樹(shù)（回溯算法）遍歷框架
for(charj=0;j1,res);
path.deleteCharAt(path.length()-1);
}
}else{
//pattern[i]是普通字符c
path.append(c);
traverse(node.children[c],path,pattern,i+1,res);
path.deleteCharAt(path.length()-1);
}
}

下面這個(gè) GIF 畫(huà)了匹配"t.a."的過(guò)程，應(yīng)該就容易理解上述代碼的邏輯了：

可以看到，keysWithPattern和keysWithPrefix的實(shí)現(xiàn)是有些類(lèi)似的，而且這兩個(gè)函數(shù)還有一個(gè)潛在的特性：它們返回的結(jié)果列表一定是符合「字典序」的。

原因應(yīng)該不難理解，每一個(gè)節(jié)點(diǎn)的children數(shù)組都是從左到右進(jìn)行遍歷，即按照 ASCII 碼從小到大的順序遞歸遍歷，得到的結(jié)果自然是符合字典序的。

好，現(xiàn)在我們實(shí)現(xiàn)了keysWithPattern方法得到模式串匹配的所有鍵，那你是否可以實(shí)現(xiàn)hasKeyWithPattern方法，僅僅判斷是否存在鍵匹配模式串？

//一個(gè)偷懶的實(shí)現(xiàn)
publicbooleanhasKeyWithPattern(Stringpattern){
return!keysWithPattern(pattern).isEmpty();
}

這是一個(gè)偷懶的實(shí)現(xiàn)，因?yàn)樗膹?fù)雜度比較高。我們的目的僅僅是判斷是否存在匹配模式串的鍵，你卻把所有匹配的鍵都算出來(lái)了，這顯然是沒(méi)有必要的。

我們只需稍微改寫(xiě)一下keysWithPattern方法就可以高效實(shí)現(xiàn)hasKeyWithPattern方法：

//判斷是和否存在前綴為prefix的鍵
publicbooleanhasKeyWithPattern(Stringpattern){
//從root節(jié)點(diǎn)開(kāi)始匹配pattern[0..]
returnhasKeyWithPattern(root,pattern,0);
}

//函數(shù)定義：從 node 節(jié)點(diǎn)開(kāi)始匹配 pattern[i..]，返回是否成功匹配
privatebooleanhasKeyWithPattern(TrieNodenode,Stringpattern,inti){
if(node==null){
//樹(shù)枝不存在，即匹配失敗
returnfalse;
}
if(i==pattern.length()){
//模式串走到頭了，看看匹配到的是否是一個(gè)鍵
returnnode.val!=null;
}
charc=pattern.charAt(i);
//沒(méi)有遇到通配符
if(c!='.'){
//從node.children[c]節(jié)點(diǎn)開(kāi)始匹配pattern[i+1..]
returnhasKeyWithPattern(node.children[c],pattern,i+1);
}
//遇到通配符
for(intj=0;j//pattern[i]可以變化成任意字符，嘗試所有可能，只要遇到一個(gè)匹配成功就返回
if(hasKeyWithPattern(node.children[j],pattern,i+1)){
returntrue;
}
}
//都沒(méi)有匹配
returnfalse;
}

有之前的鋪墊，這個(gè)實(shí)現(xiàn)應(yīng)該是不難理解的，類(lèi)似于回溯算法解數(shù)獨(dú)游戲中找到一個(gè)可行解就提前結(jié)束遞歸的做法。

到這里，TrieMap的所有和前綴相關(guān)的方法都實(shí)現(xiàn)完了，還剩下put和remove這兩個(gè)基本方法了，其實(shí)它們的難度不大，就是遞歸修改數(shù)據(jù)結(jié)構(gòu)的那一套，如果不熟悉的話可以參見(jiàn)二叉搜索樹(shù)基本操作。

先說(shuō)put方法的實(shí)現(xiàn)吧，直接看代碼：

//在map中添加或修改鍵值對(duì)
publicvoidput(Stringkey,Vval){
if(!containsKey(key)){
//新增鍵值對(duì)
size++;
}
//需要一個(gè)額外的輔助函數(shù)，并接收其返回值
root=put(root,key,val,0);
}

//定義：向以 node 為根的 Trie 樹(shù)中插入 key[i..]，返回插入完成后的根節(jié)點(diǎn)
privateTrieNodeput(TrieNodenode,Stringkey,Vval,inti){
if(node==null){
//如果樹(shù)枝不存在，新建
node=newTrieNode<>();
}
if(i==key.length()){
//key的路徑已插入完成，將值val存入節(jié)點(diǎn)
node.val=val;
returnnode;
}
charc=key.charAt(i);
//遞歸插入子節(jié)點(diǎn)，并接收返回值
node.children[c]=put(node.children[c],key,val,i+1);
returnnode;
}

因?yàn)槭沁f歸修改數(shù)據(jù)結(jié)構(gòu)，所以我們必須額外創(chuàng)建一個(gè)返回類(lèi)型為TrieNode的輔助函數(shù)，并且在遞歸調(diào)用的時(shí)候接收其返回值，拼接到父節(jié)點(diǎn)上。

前文說(shuō)了，Trie 樹(shù)中的鍵就是「樹(shù)枝」，值就是「節(jié)點(diǎn)」，所以插入的邏輯就是沿路新建「樹(shù)枝」，把key的整條「樹(shù)枝」構(gòu)建出來(lái)之后，在樹(shù)枝末端的「節(jié)點(diǎn)」中存儲(chǔ)val：

最后，我們說(shuō)一下remove函數(shù)，似乎所有數(shù)據(jù)結(jié)構(gòu)的刪除操作相對(duì)其他操作都會(huì)更復(fù)雜一些。

比如說(shuō)下圖這個(gè)場(chǎng)景，如果你想刪除鍵"team"，那么需要?jiǎng)h掉"eam"這條樹(shù)枝才是符合邏輯的：

刪多了肯定不行，但刪少了也不行，否則前文實(shí)現(xiàn)的hasKeyWithPrefix就會(huì)出錯(cuò)。

那么如何控制算法來(lái)正確地進(jìn)行刪除呢？

首先，遞歸修改數(shù)據(jù)結(jié)構(gòu)的時(shí)候，如果一個(gè)節(jié)點(diǎn)想刪掉自己，直接返回空指針就行了。

其次，一個(gè)節(jié)點(diǎn)如何知道自己是否需要被刪除呢？主要看自己的val字段是否為空以及自己的children數(shù)組是否全都是空指針。

這里就要利用前文手把手刷二叉樹(shù)（總結(jié)篇）中說(shuō)到的后序位置的特點(diǎn)了：

一個(gè)節(jié)點(diǎn)要先遞歸處理子樹(shù)，然后在后序位置檢查自己的val字段和children列表，判斷自己是否需要被刪除。

如果自己的val字段為空，說(shuō)明自己沒(méi)有存儲(chǔ)值，如果同時(shí)自己的children數(shù)組全是空指針，說(shuō)明自己下面也沒(méi)有接樹(shù)枝，即不是任何一個(gè)鍵的前綴。這種情況下這個(gè)節(jié)點(diǎn)就沒(méi)有存在的意義了，應(yīng)該刪掉自己。

直接看代碼：

//在Map中刪除key
publicvoidremove(Stringkey){
if(!containsKey(key)){
return;
}
//遞歸修改數(shù)據(jù)結(jié)構(gòu)要接收函數(shù)的返回值
root=remove(root,key,0);
size--;
}

//定義：在以 node 為根的 Trie 樹(shù)中刪除 key[i..]，返回刪除后的根節(jié)點(diǎn)
privateTrieNoderemove(TrieNodenode,Stringkey,inti){
if(node==null){
returnnull;
}
if(i==key.length()){
//找到了key對(duì)應(yīng)的TrieNode，刪除val
node.val=null;
}else{
charc=key.charAt(i);
//遞歸去子樹(shù)進(jìn)行刪除
node.children[c]=remove(node.children[c],key,i+1);
}
//后序位置，遞歸路徑上的節(jié)點(diǎn)可能需要被清理
if(node.val!=null){
//如果該TireNode存儲(chǔ)著val，不需要被清理
returnnode;
}
//檢查該TrieNode是否還有后綴
for(intc=0;cif(node.children[c]!=null){
//只要存在一個(gè)子節(jié)點(diǎn)（后綴樹(shù)枝），就不需要被清理
returnnode;
}
}
//既沒(méi)有存儲(chǔ)val，也沒(méi)有后綴樹(shù)枝，則該節(jié)點(diǎn)需要被清理
returnnull;
}

到這里，TrieMap的所有 API 就實(shí)現(xiàn)完了，完整代碼如下：

classTrieMap<V>{
//ASCII碼個(gè)數(shù)
privatestaticfinalintR=256;
//當(dāng)前存在Map中的鍵值對(duì)個(gè)數(shù)
privateintsize=0;
//Trie樹(shù)的根節(jié)點(diǎn)
privateTrieNoderoot=null;

privatestaticclassTrieNode<V>{
Vval=null;
TrieNode[]children=newTrieNode[R];
}

/*****增/改*****/

//在map中添加或修改鍵值對(duì)
publicvoidput(Stringkey,Vval){
if(!containsKey(key)){
//新增鍵值對(duì)
size++;
}
//需要一個(gè)額外的輔助函數(shù)，并接收其返回值
root=put(root,key,val,0);
}

//定義：向以 node 為根的 Trie 樹(shù)中插入 key[i..]，返回插入完成后的根節(jié)點(diǎn)
privateTrieNodeput(TrieNodenode,Stringkey,Vval,inti){
if(node==null){
//如果樹(shù)枝不存在，新建
node=newTrieNode<>();
}
if(i==key.length()){
//key的路徑已插入完成，將值val存入節(jié)點(diǎn)
node.val=val;
returnnode;
}
charc=key.charAt(i);
//遞歸插入子節(jié)點(diǎn)，并接收返回值
node.children[c]=put(node.children[c],key,val,i+1);
returnnode;
}

/*****刪*****/

//在Map中刪除key
publicvoidremove(Stringkey){
if(!containsKey(key)){
return;
}
//遞歸修改數(shù)據(jù)結(jié)構(gòu)要接收函數(shù)的返回值
root=remove(root,key,0);
size--;
}

//定義：在以 node 為根的 Trie 樹(shù)中刪除 key[i..]，返回刪除后的根節(jié)點(diǎn)
privateTrieNoderemove(TrieNodenode,Stringkey,inti){
if(node==null){
returnnull;
}
if(i==key.length()){
//找到了key對(duì)應(yīng)的TrieNode，刪除val
node.val=null;
}else{
charc=key.charAt(i);
//遞歸去子樹(shù)進(jìn)行刪除
node.children[c]=remove(node.children[c],key,i+1);
}
//后序位置，遞歸路徑上的節(jié)點(diǎn)可能需要被清理
if(node.val!=null){
//如果該TireNode存儲(chǔ)著val，不需要被清理
returnnode;
}
//檢查該TrieNode是否還有后綴
for(intc=0;cif(node.children[c]!=null){
//只要存在一個(gè)子節(jié)點(diǎn)（后綴樹(shù)枝），就不需要被清理
returnnode;
}
}
//既沒(méi)有存儲(chǔ)val，也沒(méi)有后綴樹(shù)枝，則該節(jié)點(diǎn)需要被清理
returnnull;
}

/*****查*****/

//搜索key對(duì)應(yīng)的值，不存在則返回null
publicVget(Stringkey){
//從root開(kāi)始搜索key
TrieNodex=getNode(root,key);
if(x==null||x.val==null){
//x為空或x的val字段為空都說(shuō)明key沒(méi)有對(duì)應(yīng)的值
returnnull;
}
returnx.val;
}

//判斷key是否存在在Map中
publicbooleancontainsKey(Stringkey){
returnget(key)!=null;
}

//判斷是和否存在前綴為prefix的鍵
publicbooleanhasKeyWithPrefix(Stringprefix){
//只要能找到一個(gè)節(jié)點(diǎn)，就是存在前綴
returngetNode(root,prefix)!=null;
}

//在所有鍵中尋找query的最短前綴
publicStringshortestPrefixOf(Stringquery){
TrieNodep=root;
//從節(jié)點(diǎn)node開(kāi)始搜索key
for(inti=0;iif(p==null){
//無(wú)法向下搜索
return"";
}
if(p.val!=null){
//找到一個(gè)鍵是query的前綴
returnquery.substring(0,i);
}
//向下搜索
charc=query.charAt(i);
p=p.children[c];
}

if(p!=null&&p.val!=null){
//如果query本身就是一個(gè)鍵
returnquery;
}
return"";
}

//在所有鍵中尋找query的最長(zhǎng)前綴
publicStringlongestPrefixOf(Stringquery){
TrieNodep=root;
//記錄前綴的最大長(zhǎng)度
intmax_len=0;

//從節(jié)點(diǎn)node開(kāi)始搜索key
for(inti=0;iif(p==null){
//無(wú)法向下搜索
break;
}
if(p.val!=null){
//找到一個(gè)鍵是query的前綴，更新前綴的最大長(zhǎng)度
max_len=i;
}
//向下搜索
charc=query.charAt(i);
p=p.children[c];
}

if(p!=null&&p.val!=null){
//如果query本身就是一個(gè)鍵
returnquery;
}
returnquery.substring(0,max_len);
}

//搜索前綴為prefix的所有鍵
publicListkeysWithPrefix(Stringprefix){
Listres=newLinkedList<>();
//找到匹配prefix在Trie樹(shù)中的那個(gè)節(jié)點(diǎn)
TrieNodex=getNode(root,prefix);
if(x==null){
returnres;
}
//DFS遍歷以x為根的這棵Trie樹(shù)
traverse(x,newStringBuilder(prefix),res);
returnres;
}

//遍歷以node節(jié)點(diǎn)為根的Trie樹(shù)，找到所有鍵
privatevoidtraverse(TrieNodenode,StringBuilderpath,Listres){
if(node==null){
//到達(dá)Trie樹(shù)底部葉子結(jié)點(diǎn)
return;
}

if(node.val!=null){
//找到一個(gè)key，添加到結(jié)果列表中
res.add(path.toString());
}

//回溯算法遍歷框架
for(charc=0;c//做選擇
path.append(c);
traverse(node.children[c],path,res);
//撤銷(xiāo)選擇
path.deleteCharAt(path.length()-1);
}
}

//通配符.匹配任意字符
publicListkeysWithPattern(Stringpattern){
Listres=newLinkedList<>();
traverse(root,newStringBuilder(),pattern,0,res);
returnres;
}

//遍歷函數(shù)，嘗試在「以node為根的Trie樹(shù)中」匹配pattern[i..]
privatevoidtraverse(TrieNodenode,StringBuilderpath,Stringpattern,inti,Listres){
if(node==null){
//樹(shù)枝不存在，即匹配失敗
return;
}
if(i==pattern.length()){
//pattern匹配完成
if(node.val!=null){
//如果這個(gè)節(jié)點(diǎn)存儲(chǔ)著val，則找到一個(gè)匹配的鍵
res.add(path.toString());
}
return;
}
charc=pattern.charAt(i);
if(c=='.'){
//pattern[i]是通配符，可以變化成任意字符
//多叉樹(shù)（回溯算法）遍歷框架
for(charj=0;j1,res);
path.deleteCharAt(path.length()-1);
}
}else{
//pattern[i]是普通字符c
path.append(c);
traverse(node.children[c],path,pattern,i+1,res);
path.deleteCharAt(path.length()-1);
}
}

//判斷是和否存在前綴為prefix的鍵
publicbooleanhasKeyWithPattern(Stringpattern){
//從root節(jié)點(diǎn)開(kāi)始匹配pattern[0..]
returnhasKeyWithPattern(root,pattern,0);
}

//函數(shù)定義：從 node 節(jié)點(diǎn)開(kāi)始匹配 pattern[i..]，返回是否成功匹配
privatebooleanhasKeyWithPattern(TrieNodenode,Stringpattern,inti){
if(node==null){
//樹(shù)枝不存在，即匹配失敗
returnfalse;
}
if(i==pattern.length()){
//模式串走到頭了，看看匹配到的是否是一個(gè)鍵
returnnode.val!=null;
}
charc=pattern.charAt(i);
//沒(méi)有遇到通配符
if(c!='.'){
//從node.children[c]節(jié)點(diǎn)開(kāi)始匹配pattern[i+1..]
returnhasKeyWithPattern(node.children[c],pattern,i+1);
}
//遇到通配符
for(intj=0;j//pattern[i]可以變化成任意字符，嘗試所有可能，只要遇到一個(gè)匹配成功就返回
if(hasKeyWithPattern(node.children[j],pattern,i+1)){
returntrue;
}
}
//都沒(méi)有匹配
returnfalse;
}

//從節(jié)點(diǎn)node開(kāi)始搜索key，如果存在返回對(duì)應(yīng)節(jié)點(diǎn)，否則返回null
privateTrieNodegetNode(TrieNodenode,Stringkey){
TrieNodep=node;
//從節(jié)點(diǎn)node開(kāi)始搜索key
for(inti=0;iif(p==null){
//無(wú)法向下搜索
returnnull;
}
//向下搜索
charc=key.charAt(i);
p=p.children[c];
}
returnp;
}

publicintsize(){
returnsize;
}
}

接下來(lái)我們只要對(duì)TrieMap做簡(jiǎn)單的封裝，即可實(shí)現(xiàn)TrieSet：

classTrieSet{
//底層用一個(gè)TrieMap，鍵就是TrieSet，值僅僅起到占位的作用
//值的類(lèi)型可以隨便設(shè)置，我參考Java標(biāo)準(zhǔn)庫(kù)設(shè)置成Object
privatefinalTrieMap