題目鏈接

/**

? ? ? ? Trie前綴樹基本結構:

? ? ? ? ? ? ? ? ? ? ? ? (多叉單詞查找樹)每個Trie中包含一個Trie數組與一個結束標識

? ? ? ? ? ? ? ? ? ? ? ? Trie[] children Trie數組,每個節點都可存放一個Trie,其索引代表該節點對應的字符。

? ? ? ? ? ? ? ? ? ? ? ? boolean isEnd 結束標識, 代表當前節點是否是一個完整單詞的結尾巴

? ? ? ? 前綴樹insert流程:

? ? ? ? ? ? ? ? ? ? ? ? 計算第一個字符的索引位置,判斷根節點的Trie節點數組中是否已有該字符(對應位置不為null,有Trie節點)

? ? ? ? ? ? ? ? ? ? ? ? 若沒有則創建新的節點賦值到對應位置,有則迭代Trie節點與字符按上述流程繼續處理

? ? ? ? ? ? ? ? ? ? ? ? 按上述流程迭代字符與Trie節點,直到處理到最后一個字符,將isEnd設置為true

? ? ? ? ?前綴樹search流程:

? ? ? ? ? ? ? ? ? ? ? ? 計算第一個字符的索引位置,判斷根節點的Trie節點數組是否已有該字符(對應位置不為null,有Trie節點)

? ? ? ? ? ? ? ? ? ? ? ? 有則迭代字符與Trie節點,重復上述流程;無則返回false

? ? ? ? ? ? ? ? ? ? ? ? 直到迭代到最后一個字符,判斷isEnd是否為true,若不為true也返回false(只是在某個單詞中出現了相同的部分)

? ? ? ? 前綴樹startsWith流程:

? ? ? ? ? ? ? ? ? ? ? ? 計算第一個字符的索引位置,判斷根節點的Trie節點數組是否已有該字符(對應位置不為null,有Trie節點)

? ? ? ? ? ? ? ? ? ? ? ? 有則迭代字符與Trie節點,重復上述流程;無則返回false

? ? ? ? ? ? ? ? ? ? ? ? 直到最后一個字符也存在(只判斷有無該前綴,無需判斷isEnd)

? ? ? ? 可抽取的公共方法:(查找前綴)

? ? ? ? ? ? ? ? ? ? ? ? 計算第一個字符的索引位置,判斷根節點的Trie節點數組是否已有該字符(對應位置不為null,有Trie節點)

? ? ? ? ? ? ? ? ? ? ? ? 有則迭代字符與Trie節點,重復上述流程; 返回最后一個節點

? ? ? ? ? ? ? ? ? ? ? ? search搜尋到最后一個節點判斷其isEnd即可

? ? ? ? ? ? ? ? ? ? ? ? startsWith搜尋到最后一個節點判斷是否為空即可

*/

class Trie {/**Trie前綴樹基本結構:(多叉單詞查找樹)每個Trie中包含一個Trie數組與一個結束標識Trie[] children Trie數組,每個節點都可存放一個Trie,其索引代表該節點對應的字符。boolean isEnd 結束標識, 代表當前節點是否是一個完整單詞的結尾巴前綴樹insert流程:計算第一個字符的索引位置,判斷根節點的Trie節點數組中是否已有該字符(對應位置不為null,有Trie節點)若沒有則創建新的節點賦值到對應位置,有則迭代Trie節點與字符按上述流程繼續處理按上述流程迭代字符與Trie節點,直到處理到最后一個字符,將isEnd設置為true前綴樹search流程:計算第一個字符的索引位置,判斷根節點的Trie節點數組是否已有該字符(對應位置不為null,有Trie節點)有則迭代字符與Trie節點,重復上述流程;無則返回false直到迭代到最后一個字符,判斷isEnd是否為true,若不為true也返回false(只是在某個單詞中出現了相同的部分)前綴樹startsWith流程:計算第一個字符的索引位置,判斷根節點的Trie節點數組是否已有該字符(對應位置不為null,有Trie節點)有則迭代字符與Trie節點,重復上述流程;無則返回false直到最后一個字符也存在(只判斷有無該前綴,無需判斷isEnd)可抽取的公共方法:(查找前綴)計算第一個字符的索引位置,判斷根節點的Trie節點數組是否已有該字符(對應位置不為null,有Trie節點)有則迭代字符與Trie節點,重復上述流程; 返回最后一個節點search搜尋到最后一個節點判斷其isEnd即可startsWith搜尋到最后一個節點判斷是否為空即可*///節點數組private Trie[] children;//結束標識boolean isEnd;//公共方法private Trie searchPrefix(String prefix) {Trie node = this; //讀取當前節點for(char ch : prefix.toCharArray()) {//計算當前字符索引位置int index = ch - 'a'; //迭代node = node.children[index];if(node == null) { //若為空代表已中斷直接結束即可break;}}return node;}public Trie() {children = new Trie[26]; //一共26個字符isEnd = false; //結束標識默認為false}public void insert(String word) {Trie node = this; //讀取當前節點for(char ch : word.toCharArray()) {//計算當前字符索引位置int index = ch - 'a'; //若當前節點的Trie節點數組中不存在該字符if(node.children[index] == null) {Trie son = new Trie();node.children[index] = son;}//迭代(存在則直接迭代)node = node.children[index]; }node.isEnd = true; //設置結束標識}public boolean search(String word) {//一直讀取到最后一個字符 判斷isEnd即可Trie node = searchPrefix(word);if(node != null) {return node.isEnd;}return false; }public boolean startsWith(String prefix) {//一直讀取到最后一個字符 判斷是否為空即可if(searchPrefix(prefix) != null) {return true;}return false;}
}/*** 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);*/