Trie 樹也稱為字典樹、單詞查找樹，最大的特點(diǎn)就是共享字符串的公共前綴唠摹，這樣可以達(dá)到節(jié)省空間的目的。像我們?cè)谑褂盟阉饕孑斎肽承╆P(guān)鍵字的時(shí)候奉瘤，搜索引擎會(huì)自動(dòng)彈出一些相關(guān)的信息勾拉，這些都是通過 Trie 樹實(shí)現(xiàn)的。
Trie 樹的數(shù)據(jù)結(jié)構(gòu)
Trie 樹的根節(jié)點(diǎn)不存任何數(shù)據(jù)盗温，每個(gè)分支都代表一個(gè)完整的字符串藕赞。來看看 Trie 樹的結(jié)構(gòu)：
從上圖可以歸納出Trie樹的基本性質(zhì)：
- 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)子節(jié)點(diǎn)都包含一個(gè)字符卖局。
- 從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)斧蜕，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串砚偶。
- 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符互不相同批销。
- 從第一字符開始有連續(xù)重復(fù)的字符只占用一個(gè)節(jié)點(diǎn)，比如上面的 to 和 ten染坯，中重復(fù)的單詞 t 只占用了一個(gè)節(jié)點(diǎn)均芽。
從這幾條基本性質(zhì)我們可以抽象出節(jié)點(diǎn)的 class 屬性：
- 是否為葉子節(jié)點(diǎn)的標(biāo)志位 isWord。
- 既能存儲(chǔ)當(dāng)前節(jié)點(diǎn)的值也能存儲(chǔ)其所有的子節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)HashMap单鹿。
先從稍微簡(jiǎn)單的實(shí)現(xiàn)開始
在 Java 中掀宋，Trie 樹可以使用 HashMap 實(shí)現(xiàn)，因?yàn)橐粋€(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)未知，而 HashMap 可以動(dòng)態(tài)擴(kuò)展劲妙，而且可以在 O(1) 的時(shí)間復(fù)雜度內(nèi)判斷某個(gè)子節(jié)點(diǎn)是否存在湃鹊。以 LeetCode 208 為例，來看看這種實(shí)現(xiàn)方式镣奋。
首先定義 Trie 樹的節(jié)點(diǎn)币呵，節(jié)點(diǎn)的結(jié)構(gòu)為 HashMap，key 為字符串中的字符侨颈，value 為這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)余赢。
class TrieNode {
// 子節(jié)點(diǎn)(key是下級(jí)字符，value是下級(jí)節(jié)點(diǎn))
private Map<Character, TrieNode> subNodes = new HashMap<>();
// 添加子節(jié)點(diǎn)
public void addSubNode(Character c, TrieNode subNode) {
subNodes.put(c, subNode);
}
// 獲取子節(jié)點(diǎn)
public TrieNode getSubNode(Character c) {
return subNodes.get(c);
}
}
再來看看 Trie 樹的主函數(shù)肛搬，在初始化樹時(shí)没佑，使用構(gòu)造函數(shù)構(gòu)造一個(gè)不存數(shù)據(jù)的根節(jié)點(diǎn)。在插入字符串時(shí)温赔，從根節(jié)點(diǎn)開始判斷樹中是否已經(jīng)包含了這個(gè)字符串的當(dāng)前字符蛤奢，如果不存在這個(gè)字符則新建節(jié)點(diǎn)保存當(dāng)前字符，插入結(jié)束的時(shí)候設(shè)置結(jié)束標(biāo)識(shí)陶贼，這里簡(jiǎn)單的用'#'來標(biāo)記啤贩。
search() 和 startsWith() 函數(shù)也是類似，從根節(jié)點(diǎn)開始查找 HashMap 中是否存在對(duì)應(yīng)的子節(jié)點(diǎn)拜秧。這兩個(gè)函數(shù)的唯一區(qū)別是在字符串遍歷完成的時(shí)候痹屹，search() 需要判斷當(dāng)前字符是否已經(jīng)走到了 Trie 樹的葉子節(jié)點(diǎn)，而 startsWith() 函數(shù)不需要枉氮。
class Trie {
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode curNode = this.root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
TrieNode subNode = curNode.getSubNode(c);
// 如果沒有這個(gè)節(jié)點(diǎn)則新建
if (subNode == null) {
subNode = new TrieNode();
curNode.addSubNode(c, subNode);
}
// 指向子節(jié)點(diǎn)志衍，進(jìn)入下一循環(huán)
curNode = subNode;
}
// 設(shè)置結(jié)束標(biāo)識(shí)
curNode.addSubNode('#', new TrieNode());
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode curNode = this.root;
for (int i = 0; i < word.length(); i++) {
curNode = curNode.getSubNode(word.charAt(i));
if (curNode == null) return false;
}
return curNode.getSubNode('#') != null;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode curNode = this.root;
for (int i = 0; i < prefix.length(); i++) {
curNode = curNode.getSubNode(prefix.charAt(i));
if (curNode == null) return false;
}
return true;
}
}
進(jìn)一步實(shí)現(xiàn)敏感詞過濾
在實(shí)現(xiàn)敏感詞過濾前，首先需要初始化 Trie 樹聊替，將所有敏感詞作為字符串全部插入到 Trie 樹中楼肪。
其實(shí)原理還是和之前一樣的，只不過相對(duì)于上面的代碼來說惹悄，我們需要多增加一個(gè)指針春叫。因?yàn)槊舾性~在字符串的位置我們是不知道的嘛，所以我們只能增加一個(gè)指針泣港，對(duì)整個(gè)字符串進(jìn)行遍歷暂殖，尋找敏感詞開始的位置，剩下的邏輯就和上面的代碼相似了当纱，如下圖所示呛每。這里假設(shè)在 Trie 樹中已經(jīng)初始化好了 bca、bcf惫东、de 這幾個(gè)敏感詞莉给。
首先 p1 指針指向 root毙石，指針 p2 和 p3 指向字符串中的第一個(gè)字符廉沮。算法從字符 a 開始颓遏，檢測(cè)有沒有以 a 作為前綴的敏感詞，在這里就直接判斷 root 中有沒有 a 這個(gè)子節(jié)點(diǎn)即可滞时。沒有的話將 p2 和 p3 同時(shí)右移叁幢，而如果存在以 a 作為前綴的敏感詞，那么就只右移 p3 繼續(xù)判斷 p2 和 p3 之間的這個(gè)字符串是否是敏感詞坪稽。如果在字符串中找到敏感詞曼玩，那么可以用其他字符串如 *** 代替。接下來不斷循環(huán)直到整個(gè)字符串遍歷完成就可以了窒百。
這樣的算法時(shí)間復(fù)雜度是多少呢黍判？構(gòu)建敏感詞的時(shí)間復(fù)雜度是可以忽略不計(jì)的，因?yàn)闃?gòu)建完成后我們是可以無數(shù)次使用的篙梢。所以我們來看看查找敏感詞的時(shí)間復(fù)雜度顷帖。如果字符串的長(zhǎng)度為 n，而每個(gè)敏感詞查找的時(shí)間復(fù)雜度是 O(m)渤滞，我們需要對(duì)字符串遍歷 n 遍贬墩，所以查找敏感詞的這個(gè)過程的時(shí)間復(fù)雜度為 O(m * n)。
