string_trie_search.cpp

class Trie {
public:
    Trie() {
        memset(children, 0, sizeof(children));
        valid = false;
    }
    
    void insert(string word) {
        // from trie root
        auto node = this;
        // for each sequence item (char) in the sequence (string) to insert
        for (auto ch : word)
        {
            // compute a key for that sequence item (char)
            auto key = ch - 'a';
            // Add trie node if not already exists for that key
            if (node->children[key] == 0)
                node->children[key] = new Trie();

            // go to next node
            node = node->children[key];
        }

        // mark that last node as terminal for that sequence
        node->valid = true;
    }
    
    bool search(string word) {
        auto node = this;
        for (auto ch : word)
        {
            auto key = ch - 'a';
            if (node->children[key] == 0)
                return false;

            node = node->children[key];
        }

        return node->valid;
    }
    
    bool startsWith(string prefix) {
        auto node = this;
        for (auto ch : prefix)
        {
            auto key = ch - 'a';
            // missing sequence item
            if (node->children[key] == 0)
                return false;
            
            node = node->children[key];
        }
        
        // all the sequence exists from 'this' trie node
        return true;
    }
    
private:
    Trie *children[26];
    bool valid;
};