我一開始想題目叫前綴樹，是要用樹嗎？但是不知道用樹怎么寫，然后我就花了10多分鐘，用了HashMap解了。map的key是word，value是一個放了word的所有前綴的set，這樣search方法就非常簡單了，只要看hashmap里面有沒有這個key就行，startsWith方法就很垃圾了，我遍歷了所有的value，如果其中一個value中有這個前綴就返回true，遍歷完了返回false，以下是我的代碼：

class Trie {private HashMap<String, Set<String>> map;public Trie() {map = new HashMap<>();}public void insert(String word) {int n = word.length();Set<String> set = new HashSet<>();int i = n;while(i>=0){String str = word.substring(0,i);set.add(str);i--;}map.put(word, set);}public boolean search(String word) {return map.containsKey(word);}public boolean startsWith(String prefix) {Set keyset = map.keySet();Iterator iterator = keyset.iterator();while(iterator.hasNext()){String key = (String)iterator.next();if(map.get(key).contains(prefix)){return true;}}return false;}
}

?我這種方法根樹沒有半毛錢關系，效率極低，看看官方題解的做法吧。

題解是真宗用的字典樹，效率非常高。先上題解代碼：

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 ch = word.charAt(i);int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];}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 ch = prefix.charAt(i);int index = ch - 'a';if (node.children[index] == null) {return null;}node = node.children[index];}return node;}
}

?它這個樹的結構非常巧妙，節點Trie表示一個小寫字母，每個節點都包含一個標致位boolean isEnd,表示這個小寫字母是不是某個單詞的結束字母，還包含一個節點數組Trie[] childern，children[0]表示‘a’..children[25]表示‘z’。

所以比如apple這個單詞可以通過字典樹表示如下：

?如果再往里面加兩個單詞，"app"和"yel"就會變成這樣：

p的isEnd變成了true，加了一個單詞“yel”，這樣就非常方便查找了。

public Trie() {children = new Trie[26];isEnd = false;}

通過構造方法我們可以看出，節點創建的時候它的isEnd是false，childre只是創建了一個數組容器，數組里面的節點是沒有創建的。

public void insert(String word) {Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}

insert方法非常簡單，就是遍歷這個word，把它的每個字母往后面添加，最后一個字母的isEnd設置成true。

private Trie searchPrefix(String prefix) {Trie node = this;for (int i = 0; i < prefix.length(); i++) {char ch = prefix.charAt(i);int index = ch - 'a';if (node.children[index] == null) {return null;}node = node.children[index];}return node;}

searchPrefix()方法作為一個輔助方法，作用是找到傳進來的這個單詞的最后一個字母。

 public boolean search(String word) {Trie node = searchPrefix(word);return node != null && node.isEnd;}

search()調用searchPrefix()方法拿到單詞的最后一個字母節點，如果這個節點不為空并且是結束，返回true。

 public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}

?startsWith()方法調用searchPrefix()方法找到前綴的最后一個字母節點，只要這個節點不為空就返回true。

這個字典樹的方法是非常的巧妙。