Trie.cpp

class Trie {
    
    struct Node{
        vector<shared_ptr<Node>> children = vector<shared_ptr<Node>>(26, nullptr);
        bool is_end = false;
    };

    shared_ptr<Node> root;
    
public:
    
    /** Initialize your data structure here. */
    Trie() : root(make_shared<Node>()){}
    
    /** Inserts a word into the trie. */
    //
    //  O(n) n : word.size()
    //
    void insert(string const& word) {
        auto curr = root;
        
        for(auto c : word){
            if(curr->children[c - 'a']){
                curr = curr->children[c - 'a'];
            }else{
                curr = curr->children[c - 'a'] = make_shared<Node>();
            }            
        }
        
        curr->is_end = true;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string const& prefix) const {
        return search(prefix, true);
    }    
    
    /** Returns if the word is in the trie. */
    bool search(string const& word) const{
        return search(word, false);
    }

    //
    //  O(n) n : word.size()
    //
    
    bool search(string const& word, bool is_prefix) const {
        auto curr = root;
        
        for(auto c : word){
            if(curr->children[c - 'a']){
                curr = curr->children[c - 'a'];
            }else{
                return false;
            }            
        }
        
        return is_prefix || curr->is_end;
    }
};