[[408420]]

本文轉載自微信公眾號「帥地玩編程」，作者帥地。轉載本文請聯系帥地玩編程公眾號。

Trie 樹大家了解一下原理和應用即可，有時候面試的時候會問到，下面我用面試的情景跟大家講解 trie 樹。

面試官：玩過王者榮耀吧?了解過敏感詞過濾嗎?，例如在游戲里，如果我們發送“你在干嘛?麻痹演員啊你?”，由于“麻痹”是一個敏感詞，所以當你把聊天發出來之后，我們會用“**”來代表“麻痹”這次詞，所以發送出來的聊天會變成這樣：“你在干嘛?**演員啊你?”。

小秋：聽說過啊，在各大社區也經常看到，例如評論一個問題等，一些粗話經常被過濾掉了。

面試官：嗯，如果我給你一段文字，以及給你一些需要過濾的敏感詞，你會怎么來實現這個敏感詞過濾的算法呢?例如我給你一段字符串“abcdefghi",以及三個敏感詞"de", "bca", "bcf"。

小秋：(敏感詞過來算法??不就是字符串匹配嗎?)我可以通過字符串匹配算法，例如在字符串”abcdefghi"在查找是否存在字串“de"，如果找到了就把”de“用"**"代替。通過三次匹配之后，接變成這樣了：“abc ** fghi"。

面試官：可以說說你采用哪種字符串匹配算法嗎?

小秋：最簡單的方法就是采用兩個for循環保留求解了，不過每次匹配的都時間復雜度為O(n*m)，我可以采用 KMP 字符串匹配算法，這樣時間復雜度是 O(m+n)。

n 表示字符串的長度，m 表示每個敏感詞的長度。

面試官：這是一個方法，對于敏感詞過濾，你還有其他方法嗎?

小秋：(其他方法?說實話，我也覺得不是采用這種 KMP 算法來匹配的了，可是，之前也沒去了解過敏感詞，這下要涼)對敏感詞過來之前也沒了解過，暫時沒想到其他方法。

trie 樹

面試官：了解過 trie 樹嗎?

小秋：(嘿嘿，數據結構這方法，我得爭氣點)了解過，我還用代碼實現過。

面試官：可以說說它的特點嗎?

小秋：trie 樹也稱為字典樹、單詞查找樹，最大的特點就是共享字符串的公共前綴來達到節省空間的目的了。例如，字符串 "abc"和"abd"構成的 trie 樹如下：

trie 樹的根節點不存任何數據，每整個個分支代表一個完整的字符串。像 abc 和 abd 有公共前綴 ab，所以我們可以共享節點 ab。如果再插入 abf，則變成這樣：

如果我再插入 bc，則是這樣(bc 和其他三個字符串沒有公共前綴)。

面試官：那如果再插入 "ab" 這個字符串呢?

小秋：差點說了，每個分支的內部可能也含有完整的字符串，所以我們可以對于那些是某個字符串結尾的節點做一個標記，例如 abc, abd,abf 都包含了字符串 ab,所以我們可以在節點 b 這里做一個標記。如下(我用紅色作為標記)：

面試官：可以說說 trie 樹有哪些應用嗎?

小秋：trie 最大的特點就是利用了字符串的公共前綴，像我們有時候在百度、谷歌輸入某個關鍵字的時候，它會給我們列舉出很多相關的信息

這種就是通過 trie 樹來實現的。

小秋：(嗯?trie 又稱為單詞查找樹，好像可以用 trie 來實現剛才的敏感詞匹配?面試官無緣無故提 trie 樹難道別有用意?)

面試官：剛才的敏感詞過濾，其實也可以采用 trie 來實現，你知道怎么實現嗎?

trie 樹來實現敏感詞過濾

小秋：(果然，面試官真是個好人啊，直接提示了，要是還不知道怎么實現，那不真涼?)我想想……..我知道了，

我可以這樣來實現：

先把你給我的三個敏感詞："de", "bca", "bcf" 建立一顆 trie 樹，如下：

接著我們可以采用三個指針來遍歷，我直接用上面你給你例子來演示吧。

1、首先指針 p1 指向 root，指針 p2 和 p3 指向字符串第一個字符

2、然后從字符串的 a 開始，檢測有沒有以 a 作為前綴的敏感詞，直接判斷 p1 的孩子節點中是否有 a 這個節點就可以了，顯然這里沒有。接著把指針 p2 和 p3 向右移動一格。

3、然后從字符串 b 開始查找，看看是否有以 b 作為前綴的字符串，p1 的孩子節點中有 b，這時，我們把 p1 指向節點 b，p2 向右移動一格，不過，p3不動。

4、判斷 p1 的孩子節點中是否存在 p2 指向的字符c，顯然有。我們把 p1 指向節點 c，p2 向右移動一格，p3不動。

5、判斷 p1 的孩子節點中是否存在 p2 指向的字符d，這里沒有。這意味著，不存在以字符b作為前綴的敏感詞。這時我們把p2和p3都移向字符c，p1 還是還原到最開始指向 root。

6、和前面的步驟一樣，判斷有沒以 c 作為前綴的字符串，顯然這里沒有，所以把 p2 和 p3 移到字符 d。

7、然后從字符串 d 開始查找，看看是否有以 d 作為前綴的字符串，p1 的孩子節點中有 d，這時，我們把 p1 指向節點 d，p2 向右移動一格，不過，p3和剛才一樣不動。(看到這里，我猜你已經懂了)

8、判斷 p1 的孩子節點中是否存在 p2 指向的字符e，顯然有。我們把 p1 指向節點 e，并且，這里e是最后一個節點了，查找結束，所以存在敏感詞de，即 p3 和 p2 這個區間指向的就是敏感詞了，把 p2 和 p3 指向的區間那些字符替換成 *。并且把 p2 和 p3 移向字符 f。如下：

9、接著還是重復同樣的步驟，知道 p3 指向最后一個字符。

復雜度分析

面試官：可以說說時間復雜度嗎?

小秋：如果敏感詞的長度為 m，則每個敏感詞的查找時間復雜度是 O(m)，字符串的長度為 n，我們需要遍歷 n 遍，所以敏感詞查找這個過程的時間復雜度是 O(n * m)。如果有 t 個敏感詞的話，構建 trie 樹的時間復雜度是 O(t * m)。

這里我說明一下，在實際的應用中，構建 trie 樹的時間復雜度我覺得可以忽略，因為 trie 樹我們可以在一開始就構建了，以后可以無數次重復利用的了。而剛才的 kmp 算法時間復雜度是 t *(m+n)，不過kmp需要維護 next 數組比較費空間，而且在實際情況中,敏感詞的數量 t 是比較大，而 n 反而比較小的吧。

10、如果讓你來 構建 trie 樹，你會用什么數據結構來實現?

小秋：我一般使用 Java，我會采用 HashMap 來實現，因為一個節點的字節點個數未知，采用 HashMap 可以動態拓展，而且可以在 O(1) 復雜度內判斷某個子節點是否存在。

面試官：嗯，回去等通知吧。

總結

今天主要將了 trie 樹以及 trie 樹的一些應用，還要就是如何通過 trie 樹來實現敏感詞的過濾，至于代碼的實現，我這里就不給出了，在實現的時候，為了防止這種”麻 痹"或者“麻￥痹”等，我們也要對特殊字符進行過濾等，有興趣的可以去實現一波。