# leetcode 208

class Node {
    public:
    unordered_map<char, Node*> child;
};

class Trie {
    Node* root;
public:
    
    Trie() {
        root = new Node();
    }
    
    void insert(string word) {
        Node* node = root;
        
        for (int i = 0; i < word.size(); i++) {
            char cur = word[i];
            if (node->child.find(cur) != node->child.end()) {
                node = node->child[cur];
                continue;
            }
            node->child[cur] = new Node();
            node = node->child[cur];
        }
        node->child['#'] = NULL;
    }
    
    bool search(string word) {
        Node* node = root;
        for (int i = 0; i < word.size(); i++) {
            char cur = word[i];
            if (node->child.find(cur) == node->child.end()) {
                return false;
            }
            node = node->child[cur];
        }
        return node->child.find('#') != node->child.end();
    }
    
    bool startsWith(string prefix) {
        Node* node = root;
        for (int i = 0; i < prefix.size(); i++) {
            char cur = prefix[i];
            if (node->child.find(cur) == node->child.end()) {
                return false;
            }
            node = node->child[cur];
        }
        return true;
    }
    
};