LeetCode 208. 实现 Trie (前缀树)

LeetCode 208. 实现 Trie (前缀树)

思路：
跟Acwing这道题一样。
AcWing 835. Trie字符串统计

建立一个树，每一个节点有26个儿子，用每个节点的end表示是不是存在这个单词

代码：

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

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */