原理
介紹
高效地存儲和查詢字符串的數據結構。所以其重點在于：存儲、查詢兩個操作。
存儲操作
示例和圖片來自：https://blog.csdn.net/qq_42024195/article/details/88364485
假設有這么幾個字符串：b，abc，abd，bcd，abcd，efg，hii。最終存儲出來的Trie圖如下圖所示：
具體是怎么存的呢？對于每一個字符串，從樹的根節點開始，依次判斷當前節點的兒子節點中是否有當前字符：
- 如果有，則進行下一個字符的判斷，同時根節點更新為該兒子節點
- 如果沒有，創建一個兒子節點為當前字符，然后根節點更新為該兒子節點
如果已經到了最后一個字符，就在對應的兒子節點進行一個標記，表示從根節點到該節點的字符組成的字符串是一個單詞。（對應圖中的紅色部分）
查詢
查詢和存儲的操作類似。對于一個給定的字符串，從樹的根節點開始，依次判斷當前節點的兒子節點中是否有當前字符：
- 如果有，則進行下一個字符的判斷，同時根節點更新為該兒子節點
- 如果沒有，則說明不存在該字符串，直接返回不存在
復雜度
時間復雜度：O(max_len(s))=O(h)，h為Trie樹的高度，即最長字符串的長度。
空間復雜度：不超過O(N * max_len(s))。
代碼實現
208. 實現 Trie (前綴樹)
class Trie {private Trie[] children; // 當前節點的所有兒子private boolean isEnd; // 當前節點是否為一個單詞的結尾public Trie() {children = new Trie[26]; // 假設字符串中都是小寫字母，那么一個節點的所有兒子最多只有26個isEnd = false;}/**存儲操作：插入一個字符串*/public void insert(String word) {Trie node = this; // 從根節點開始for(char c : word.toCharArray()) {int u = c - 'a'; // [a, z] -> [0, 25]if (node.children[u] == null) { // 當前節點node不存在兒子節點 node.children[u] = new Trie(); // 創建一個節點為當前字符} node = node.children[u]; // 更新根節點為兒子節點}node.isEnd = true;}/**查詢操作：查詢某個字符串是否在樹中。如果在樹中，可以是樹中單詞的前綴，也可以是完整的單詞*/private Trie searchPrefix(String prefix) {Trie node = this; // 從根節點開始for(char c : prefix.toCharArray()) {int u = c - 'a'; // [a, z] -> [0, 25]if (node.children[u] == null) { // 當前節點node不存在兒子節點 return null;} node = node.children[u]; // 走到兒子節點}return node;}public boolean search(String word) {// 查詢樹中是否存在完整的單詞Trie node = searchPrefix(word);return node != null && node.isEnd;}public boolean startsWith(String prefix) {// 查詢樹中是否存在某個前綴return searchPrefix(prefix) != null;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/
當然，Trie樹也可以查詢存儲并查詢一個單詞出現了幾次，只需要把isEnd改成cnt就行。當cnt為0時，表示沒出現過，即不是一個完整的單詞；當cnt > 0時，表示出現過，cnt的大小即為出現的次數。
