实现Trie（前缀树或字典树）

class Trie {
    Trie[] chileren;
    boolean isExist;
    public Trie() {
        chileren = new Trie[26];
        isExist = 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.chileren[index] == null){
                node.chileren[index] = new Trie();
            }
            node = node.chileren[index];
        }
        node.isExist = true;
    }
    public boolean search(String word) {
        Trie node = searchWorld(word);
        return node!=null && node.isExist;
    }
    public boolean startsWith(String prefix) {
        return searchWorld(prefix)!=null;
    }
    private Trie searchWorld(String str){
        Trie node = this;
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            int index = c-'a';
            if(node.chileren[index]==null){
                return null;
            }
            node = node.chileren[index];
        }
        return node;
    }
}