解法一：字典树
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() - 在计算是否有某一链的时候，返回结果为：
return node!=null && node.isEnd，要判断该node是否为最后一个
