解法一：字典树

Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：

• 指向子节点的指针数组 children。对于本题而言，数组长度为 26，即小写英文字母的数量。此时 children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。
• 布尔字段 isEnd，表示该节点是否为字符串的结尾。
  

class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;  //Trie node = this 而不是newfor(int i=0; i<word.length(); i++){char ch = word.charAt(i);int num = ch - 'a'; // 注意这里要判断node.children[num] == null)if(node.children[num] == null){node.children[num] = new Trie();}node = node.children[num];}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;}public Trie searchprefix(String prefix){Trie node = this;for(int i=0; i<prefix.length(); i++){char ch = prefix.charAt(i);int num = ch - 'a';if(node.children[num]==null){return null;}node = node.children[num];}return node;}
}

注意：

• 在插入算法中，当node.children[num] == null时（node.children[num] != null说明有相同前缀），才新建nodenode.children[num] = new Trie()
• 要Trie node = this，而不是Trie node = new Trie()