小秋今天去面試了，面試官問了一個與敏感詞過濾算法相關(guān)的問題，然而小秋對敏感詞過濾算法一點也沒聽說過辅甥。于是酝润，有了以下事情的發(fā)生…..
面試官開懟
面試官：玩過王者榮耀吧？了解過敏感詞過濾嗎璃弄？要销，例如在游戲里，如果我們發(fā)送“你在干嘛夏块？麻痹演員啊你疏咐？”，由于“麻痹”是一個敏感詞脐供，所以當(dāng)你把聊天發(fā)出來之后浑塞，我們會用“”來代表“麻痹”這次詞，所以發(fā)送出來的聊天會變成這樣：“你在干嘛政己？演員啊你酌壕？”。
小秋：聽說過啊歇由，在各大社區(qū)也經(jīng)辰龊ⅲ看到，例如評論一個問題等印蓖，一些粗話經(jīng)常被過濾掉了辽慕。
面試官：嗯，如果我給你一段文字赦肃，以及給你一些需要過濾的敏感詞溅蛉，你會怎么來實現(xiàn)這個敏感詞過濾的算法呢？例如我給你一段字符串“abcdefghi",以及三個敏感詞"de", "bca", "bcf"他宛。
小秋：（敏感詞過來算法船侧？？不就是字符串匹配嗎厅各？）我可以通過字符串匹配算法镜撩，例如在字符串”abcdefghi"在查找是否存在字串“de"，如果找到了就把”de“用""代替队塘。通過三次匹配之后袁梗，接變成這樣了：“abcfghi"。
面試官：可以說說你采用哪種字符串匹配算法嗎憔古？
小秋：最簡單的方法就是采用兩個for循環(huán)保留求解了遮怜，不過每次匹配的都時間復(fù)雜度為O(n*m)，我可以采用 KMP 字符串匹配算法鸿市，這樣時間復(fù)雜度是 O(m+n)锯梁。
n 表示字符串的長度即碗，m 表示每個敏感詞的長度。
面試官：這是一個方法陌凳，對于敏感詞過濾剥懒，你還有其他方法嗎？
小秋：（其他方法合敦？說實話初橘，我也覺得不是采用這種 KMP 算法來匹配的了，可是蛤肌，之前也沒去了解過敏感詞壁却，這下要涼）對敏感詞過來之前也沒了解過批狱，暫時沒想到其他方法裸准。
trie 樹
面試官：了解過 trie 樹嗎？
小秋：（嘿嘿赔硫，數(shù)據(jù)結(jié)構(gòu)這方法炒俱，我得爭氣點）了解過，我還用代碼實現(xiàn)過爪膊。
面試官：可以說說它的特點嗎权悟？
小秋：trie 樹也稱為字典樹、單詞查找樹推盛，最大的特點就是共享字符串的公共前綴來達到節(jié)省空間的目的了峦阁。例如，字符串 "abc"和"abd"構(gòu)成的 trie 樹如下：
trie 樹的根節(jié)點不存任何數(shù)據(jù)耘成，每整個個分支代表一個完整的字符串榔昔。像 abc 和 abd 有公共前綴 ab，所以我們可以共享節(jié)點 ab瘪菌。如果再插入 abf撒会，則變成這樣：
如果我再插入 bc，則是這樣（bc 和其他三個字符串沒有公共前綴）
面試官：那如果再插入 "ab" 這個字符串呢师妙？
小秋：差點說了诵肛，每個分支的內(nèi)部可能也含有完整的字符串，所以我們可以對于那些是某個字符串結(jié)尾的節(jié)點做一個標(biāo)記默穴，例如 abc, abd,abf 都包含了字符串 ab,所以我們可以在節(jié)點 b 這里做一個標(biāo)記怔檩。如下（我用紅色作為標(biāo)記）：
面試官：可以說說 trie 樹有哪些應(yīng)用嗎？
小秋：trie 最大的特點就是利用了字符串的公共前綴蓄诽，像我們有時候在百度珠洗、谷歌輸入某個關(guān)鍵字的時候，它會給我們列舉出很多相關(guān)的信息
這種就是通過 trie 樹來實現(xiàn)的若专。
小秋：（嗯许蓖？ trie 又稱為單詞查找樹，好像可以用 trie 來實現(xiàn)剛才的敏感詞匹配？面試官無緣無故提 trie 樹難道別有用意膊爪？）
面試官：剛才的敏感詞過濾自阱，其實也可以采用 trie 來實現(xiàn)，你知道怎么實現(xiàn)嗎米酬？
trie 樹來實現(xiàn)敏感詞過濾
小秋：（果然沛豌，面試官真是個好人啊，直接提示了赃额，要是還不知道怎么實現(xiàn)加派，那不真涼？）我想想……..我知道了跳芳，我可以這樣來實現(xiàn)：
先把你給我的三個敏感詞："de", "bca", "bcf" 建立一顆 trie 樹芍锦，如下：
接著我們可以采用三個指針來遍歷，我直接用上面你給你例子來演示吧飞盆。
1娄琉、首先指針 p1 指向 root，指針 p2 和 p3 指向字符串第一個字符
2吓歇、然后從字符串的 a 開始孽水，檢測有沒有以 a 作為前綴的敏感詞，直接判斷 p1 的孩子節(jié)點中是否有 a 這個節(jié)點就可以了城看，顯然這里沒有女气。接著把指針 p2 和 p3 向右移動一格。
3测柠、然后從字符串 b 開始查找炼鞠，看看是否有以 b 作為前綴的字符串，p1 的孩子節(jié)點中有 b鹃愤，這時簇搅，我們把 p1 指向節(jié)點 b，p2 向右移動一格软吐，不過瘩将，p3不動。
4凹耙、判斷 p1 的孩子節(jié)點中是否存在 p2 指向的字符c姿现，顯然有肖抱。我們把 p1 指向節(jié)點 c吮蛹，p2 向右移動一格倚喂，p3不動。
5、判斷 p1 的孩子節(jié)點中是否存在 p2 指向的字符d无畔，這里沒有。這意味著，不存在以字符b作為前綴的敏感詞。這時我們把p2和p3都移向字符c片排，p1 還是還原到最開始指向 root。
6家卖、和前面的步驟一樣谐岁，判斷有沒以 c 作為前綴的字符串，顯然這里沒有榛臼，所以把 p2 和 p3 移到字符 d伊佃。
7、然后從字符串 d 開始查找沛善，看看是否有以 d 作為前綴的字符串航揉，p1 的孩子節(jié)點中有 d，這時金刁，我們把 p1 指向節(jié)點 b帅涂，p2 向右移動一格，不過尤蛮，p3和剛才一樣不動媳友。（看到這里，我猜你已經(jīng)懂了）
8产捞、判斷 p1 的孩子節(jié)點中是否存在 p2 指向的字符e醇锚，顯然有。我們把 p1 指向節(jié)點 e坯临，并且焊唬，這里e是最后一個節(jié)點了，查找結(jié)束看靠，所以存在敏感詞de赶促，即 p3 和 p2 這個區(qū)間指向的就是敏感詞了，把 p2 和 p3 指向的區(qū)間那些字符替換成 *挟炬。并且把 p2 和 p3 移向字符 f鸥滨。如下：
9、接著還是重復(fù)同樣的步驟辟宗，知道 p3 指向最后一個字符爵赵。
復(fù)雜度分析
面試官：可以說說時間復(fù)雜度嗎？
小秋：如果敏感詞的長度為 m泊脐，則每個敏感詞的查找時間復(fù)雜度是 O(m)空幻，字符串的長度為 n，我們需要遍歷 n 遍容客，所以敏感詞查找這個過程的時間復(fù)雜度是 O(n * m)秕铛。如果有 t 個敏感詞的話约郁，構(gòu)建 trie 樹的時間復(fù)雜度是 O(t * m)。
這里我說明一下但两，在實際的應(yīng)用中鬓梅，構(gòu)建 trie 樹的時間復(fù)雜度我覺得可以忽略，因為 trie 樹我們可以在一開始就構(gòu)建了谨湘，以后可以無數(shù)次重復(fù)利用的了绽快。
10、如果讓你來 構(gòu)建 trie 樹紧阔，你會用什么數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)坊罢？
小秋：我一般使用 Java，我會采用 HashMap 來實現(xiàn)擅耽，因為一個節(jié)點的字節(jié)點個數(shù)未知活孩，采用 HashMap 可以動態(tài)拓展，而且可以在 O(1) 復(fù)雜度內(nèi)判斷某個子節(jié)點是否存在乖仇。
面試官：嗯憾儒，回去等通知吧。
總結(jié)
今天主要將了 trie 樹以及 trie 樹的一些應(yīng)用乃沙，還要就是如何通過 trie 樹來實現(xiàn)敏感詞的過濾起趾，至于代碼的實現(xiàn)，我這里就不給出了崔涂，在實現(xiàn)的時候阳掐，為了防止這種”麻 痹"或者“麻￥痹”等始衅，我們也要對特殊字符進行過濾等冷蚂，有興趣的可以去實現(xiàn)一波。
