Untitled

#define TreeNode Node

class TreeNode {
public:
    bool isEnd;
    unordered_map<int, TreeNode*> children;
    TreeNode () : isEnd(false) {}
};

class Trie {
    TreeNode *root;
public:
    Trie() {
        root = new TreeNode; 
    }
    
    void insert(string word) {
        TreeNode *p = root;
        for (char ch : word) {
            if (p->children.find(ch) == p->children.end())
                p->children[ch] = new TreeNode;
            p = p->children[ch];
        }
        p->isEnd = true;
    }
    
    bool search(string word) {
        TreeNode *p = root;
        for (char ch : word) {
            if (p->children.find(ch) == p->children.end())
                return false;
            p = p->children[ch];
        }
        return p->isEnd;
    }
    
    bool startsWith(string prefix) {
        TreeNode *p = root;
        for (char ch : prefix) {
            if (p->children.find(ch) == p->children.end())
                return false;
            p = p->children[ch];
        }
        return true;
    }
};
#undef TreeNode

/**
 * 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);
 */