前綴樹重要的存在價值是搜索速度,典型的利用空間換時間,時間復雜度為O(n),n是樹的深度。
上圖中存儲了四個單詞:am、bad、be、so,位於葉子節點,葉子節點壹定為詞,但詞不壹定位於葉子節點。除了存儲詞的節點外,其余節點稱為前綴。如ba,在樹中並不是壹個詞,但他是bad詞的前綴,前綴的重要作用就是減少存儲空間,具有相同前綴的不同單詞,只需存儲差異部分,大大減少了空間的存儲。
我所喜歡的數據結構:
Trie常見的操作:
這個題目實在是翻譯不出來啊!題意:插入多個單詞(apple、app)給每壹個詞賦值apple=3、app=2,當輸入前綴ap時,返回以ap為前綴的所有單詞值的和。
壹段文字內替換所有以
Trie中存儲的單詞
的單詞
步驟:
步驟:
在給定的數組中兩兩項異或,找出最大的異或值。
壹個數的大小如何判斷?從高位向低位走,先遇到不為0的數最大(1000 、0100),若高位相同繼續向低位走(1000 、 1100)。
思路:
由於存儲的節點只有0、1所以修改TrieNode結構
構造Trie
遍歷查找最大異或值
給定矩陣,判斷輸入的單詞是否在矩陣中。
思路:
在給出的單詞組中,找出可以組成回文的兩個單詞組。
LeetCode