Trie

class Trie {
public:
    struct Node{
        Node(char _value='-', bool _is_end = false){
            value = _value;
            is_end = _is_end;
            letters.resize(26,nullptr);
        }
        char value;
        vector<Node*> letters;
        bool is_end;
    };
    Node* root;
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Node* cur = root;
        int i = 0;
        bool flag = true;
        for(; i < word.size(); ++i){
            if(cur->letters[word[i]-'a']){
                cur = cur->letters[word[i]-'a'];
            }else{
                flag = false;
                break;
            }
        }
        if(flag){
            if(!cur->is_end){
                cur->is_end = true;
            }
        }else{
            for(;i < word.size(); ++i){
                Node* new_node = new Node(word[i]);
                cur->letters[word[i]-'a'] = new_node;
                cur = new_node;
            }
            cur->is_end = true;
        }
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* cur = root;
        for(int i = 0; i < word.size(); ++i){
            if(cur->letters[word[i]-'a']){
                cur = cur->letters[word[i]-'a'];
            }else{
                return false;
            }
        }
        return cur->is_end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* cur = root;
        for(int i = 0; i < prefix.size(); ++i){
            if(cur->letters[prefix[i]-'a']){
                cur = cur->letters[prefix[i]-'a'];
            }else{
                return false;
            }
        }
        return true;
    }
};