算法记录——字典树Trie及其基本功能（C++/Java）

1、维护字符串集合 （字典）
2、向字符串集合中插入字符串 （建树）
3、查询字符串集合中是否有某个字符串 （查询）
4、查询字符串集合中是否有某个字符串的前缀 （查询）

class Trie {
 public:
     struct Node{
         bool is_end;
         Node *son[26];
         Node(){
             is_end = false;
             for(int i=0;i<26;i++)
                 son[i] = NULL;
         }
     }*root;
     
     Trie() {
         root = new Node();
     }
     
     void insert(string word) {
         auto p = root;
         for(auto c : word){
             int u = c - 'a';
             if(!p->son[u]) p->son[u] = new Node();
             p = p->son[u];
         }
         p->is_end = true;
     }
     
     bool search(string word) {
         auto p = root;
         for(auto c : word){
             int u = c - 'a';
             if(!p->son[u]) return false;
             p = p->son[u];
         }
         return p->is_end;
     }
     
     bool startsWith(string prefix) {
         auto p = root;
         for(auto c : prefix){
             int u = c -'a';
             if(!p->son[u]) return false;
             p = p->son[u];
         }
         return true;
     }
 };

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;
    }
}