小秋今天去面試了,面試官問了一個與敏感詞過濾演算法相關的問題,然而小秋對敏感詞過濾演算法一點也沒聽說過。於是,有了以下事情的發生…..
面試官開懟
面試官:玩過王者榮耀吧?了解過敏感詞過濾嗎?,例如在遊戲里,如果我們發送「你在幹嘛?麻痹演員啊你?」,由於「麻痹」是一個敏感詞,所以當你把聊天發出來之後,我們會用「」來代表「麻痹」這次詞,所以發送出來的聊天會變成這樣:「你在幹嘛?演員啊你?」。
小秋:聽說過啊,在各大社區也經常看到,例如評論一個問題等,一些粗話經常被過濾掉了。
面試官:嗯,如果我給你一段文字,以及給你一些需要過濾的敏感詞,你會怎麼來實現這個敏感詞過濾的演算法呢?例如我給你一段字元串「abcdefghi",以及三個敏感詞"de", "bca", "bcf"。
小秋:(敏感詞過來演算法??不就是字元串匹配嗎?)我可以通過字元串匹配演算法,例如在字元串」abcdefghi"在查找是否存在字串「de",如果找到了就把」de「用""代替。通過三次匹配之後,接變成這樣了:「abcfghi"。
面試官:可以說說你採用哪種字元串匹配演算法嗎?
小秋:最簡單的方法就是採用兩個for循環保留求解了,不過每次匹配的都時間複雜度為O(n*m),我可以採用 KMP 字元串匹配演算法,這樣時間複雜度是 O(m+n)。
n 表示字元串的長度,m 表示每個敏感詞的長度。
面試官:這是一個方法,對於敏感詞過濾,你還有其他方法嗎?
小秋:(其他方法?說實話,我也覺得不是採用這種 KMP 演算法來匹配的了,可是,之前也沒去了解過敏感詞,這下要涼)對敏感詞過來之前也沒了解過,暫時沒想到其他方法。
trie 樹
面試官:了解過 trie 樹嗎?
小秋:(嘿嘿,數據結構這方法,我得爭氣點)了解過,我還用代碼實現過。
面試官:可以說說它的特點嗎?
小秋:trie 樹也稱為字典樹、單詞查找樹,最大的特點就是共享字元串的公共前綴來達到節省空間的目的了。例如,字元串 "abc"和"abd"構成的 trie 樹如下: