208. 实现 Trie (前缀树) (opens new window)

主要理解前缀树这种数据结构，每个节点代表一个字母的信息，因为具有相同前缀的单词在前缀树存储时，会共用所有前缀节点。因此每个字母节点需要有一个Trie数组作为成员属性，记录以当前字母作为前缀内容的所有分支;同时用一个布尔类型字段记录当前字母是否作为单词的结尾。具体如下：

class Trie {
    private boolean isEnd;
    private Trie[] child;
    public Trie() {
        child=new Trie[26];
        isEnd=false;
    }
    
    public void insert(String word) {
        Trie root=this;
        for(int i=0;i<word.length();i++){
            if(root.child[word.charAt(i)-'a']==null){
                root.child[word.charAt(i)-'a']=new Trie();
            }
            root=root.child[word.charAt(i)-'a'];
        }
        root.isEnd=true;

    }
    
    public boolean search(String word) {
        Trie root=this;
        for(int i=0;i<word.length();i++){
            if(root.child[word.charAt(i)-'a']==null){
                return false;
            }
            root = root.child[word.charAt(i) - 'a'];
        }
        if(root.isEnd) return true;
        else return false;

    }
    
    public boolean startsWith(String prefix) {
        Trie root=this;
        for(int i=0;i<prefix.length();i++){
            if(root.child[prefix.charAt(i)-'a']==null){
               return false;
            }
            root=root.child[prefix.charAt(i)-'a'];
        }
        return true;

    }
}