Trie 樹的定義：
? ? Trie 樹毁欣，即字典樹，又稱前綴樹岳掐，是一種多叉樹結(jié)構(gòu)凭疮。典型的應(yīng)用是用于統(tǒng)計和排序大量的字符串，它的優(yōu)點(diǎn)是：最大限度地減少無謂的字符串比較串述，查詢效率比哈希表高执解。
Trie 樹的基本性質(zhì)：
1、根節(jié)點(diǎn)不包含字符纲酗，除根節(jié)點(diǎn)外每一個節(jié)點(diǎn)都只包含一個字符材鹦。
2、從根節(jié)點(diǎn)到某一個節(jié)點(diǎn)耕姊，路徑上經(jīng)過的字符連接起來桶唐，為該節(jié)點(diǎn)對應(yīng)的字符串。
3茉兰、每個節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同尤泽。
Trie 樹的結(jié)構(gòu)：
Node節(jié)點(diǎn)：表示Trie 樹的每個節(jié)點(diǎn)，里面 isWord 表示該節(jié)點(diǎn)是否是一個單詞的末尾；next 是下一個元素的映射坯约。外層是根節(jié)點(diǎn) root 信息熊咽，以及Trie 樹中存儲的單詞數(shù)量。
Trie 樹中添加一個新的單詞：
????思路：先把 root 節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn) cur闹丐，遍歷新增單詞的每個字符横殴，判斷 cur.next 的Map 映射中是否包含當(dāng)前字符，如果不包含卿拴，則新增一個映射關(guān)系衫仑，然后將 cur = cur.next.get(c)，進(jìn)行下一個循環(huán)堕花。循環(huán)結(jié)束文狱，說明走到了單詞末尾，此時需要根據(jù)cur.isWord 判斷是否已經(jīng)存在這個單詞缘挽，如果為 cur.isWord == True瞄崇，說明已經(jīng)存在，則不執(zhí)行添加操作壕曼，否則執(zhí)行添加操作苏研。?
在Trie 中是否包含某個單詞：
????思路：思路跟 add 類似，只是在判斷cur.next.containsKey(c)中腮郊，為false時楣富，直接返回 fasle，循環(huán)結(jié)束之后伴榔，要看單詞末尾元素的isWord 是否為True纹蝴，只有為True，才能說明包含這個單詞踪少，否則可能只是一個單詞的前綴塘安。?
在 Trie 中查詢是否存在某個單詞是有prefix 為前綴的：
????思路：思路跟 contains類似，只是循環(huán)結(jié)束后援奢，無論最后一個元素是否是單詞的末尾兼犯，都被認(rèn)為是前綴。
在 Trie 中查找某個單詞是否存在集漾，其中 '. ' 代表任意一個字符：
????思路：由于前面的操作都是規(guī)范的字符串切黔，所以能夠通過cur = cur.next.get(c) 來遍歷所有元素，但是本方法有特殊字符 '.'具篇，無法通過該字符纬霞，找到下一個結(jié)點(diǎn)，所以驱显，必須采用遞歸的思想诗芜。match(Node node, String word, int index)瞳抓，以node為根節(jié)點(diǎn)的Trie 中查找單詞word中的下標(biāo)為index的字符。遞歸終止條件為：index == word.length()伏恐，字符串走完了孩哑，判斷最后一個結(jié)點(diǎn)node是否是單詞末尾；然后對 字符c 與 '.' 進(jìn)行單獨(dú)判斷翠桦，如果c 横蜒！= '.'，則node = node.next.get(c)销凑，繼續(xù)遞歸執(zhí)行丛晌；如果 c == '.'，則需要遍歷當(dāng)前node下所有的節(jié)點(diǎn)闻鉴，然后每個節(jié)點(diǎn)遞歸執(zhí)行，只要有一個節(jié)點(diǎn)的遞歸結(jié)果為true茂洒，就認(rèn)為已經(jīng)匹配上了孟岛。
