LeetCode 208. 實現(xiàn) Trie (前綴樹)

題目描述

Trie（發(fā)音類似 “try”）或者說 前綴樹 是一種樹形數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲和檢索字符串數(shù)據(jù)集中的鍵。這一數(shù)據(jù)結(jié)構(gòu)有相當多的應用情景，例如自動補全和拼寫檢查。
請你實現(xiàn) Trie 類：
Trie() 初始化前綴樹對象。
void insert(String word) 向前綴樹中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前綴樹中，返回 true（即，在檢索之前已經(jīng)插入）；否則，返回 false 。
boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix ，返回 true ；否則，返回 false 。
示例：
輸入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
輸出
[null, null, true, false, true, null, true]

思路

思路類似于一個26叉樹，每一個節(jié)點存儲的是一個字母。
插入就是沿著這個路徑不斷向下走，或創(chuàng)建下一層的26叉節(jié)點（僅當[i]下面一層的節(jié)點為空時創(chuàng)建）。當且僅當遍歷到單詞的最后一個字符時將isEnd標志位為true。
search和startwith實際上都可以依賴于一個前綴搜索方法“searchPrefix”。在前綴搜索方法中，對于給定的字符串word，從前綴樹一層一層向下搜索，具體來說，用for循環(huán)遍歷word，if(node.children[prefix.charAt(i)-‘a(chǎn)’]!=null){node=node.children[prefix.charAt(i)-‘a(chǎn)’]}，如果出現(xiàn)這個孩子節(jié)點為null，則說明該前綴不存在，return null
search就是看返回結(jié)果是否為null&&該結(jié)果的isEnd標志位是否為True
startwith只需要判斷返回結(jié)果是否為null就好

代碼

class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for (int i = 0; i < word.length(); i++){char c = word.charAt(i);int index = c - 'a';if (node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];// node移動到下面一層}node.isEnd = true;}public boolean search(String word) {Trie node = searchPrefix(word);return node != null && node.isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}private Trie searchPrefix(String prefix){Trie node = this;for (int i = 0; i < prefix.length(); i++){char c = prefix.charAt(i);int index = c - 'a';if (node.children[index] == null){return null;}node = node.children[index];}return node;}
}/*** 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);*/