208. Implement Trie (Prefix Tree)

class TrieNode { public: TrieNode() : terminate(false), children(26, nullptr){} ~TrieNode(){ for (TrieNode * child : children){ if (child) delete child; // deconstructor } } private: bool terminate; vector<TrieNode*> children; }; class Trie { public: /** Initialize your data structure here. */ Trie() { root = new TrieNode(); // initialize a root node } /** Inserts a word into the trie. */ void insert(const string & word) { TrieNode * ptr = root; for (char c: word){ // iterate char by char. a child is determined by its position. size_t pos = c - 'a'; // if this char has not been seen before in this position initiaze a new pos if (ptr->children[pos] == nullptr) ptr->children[pos] = new TrieNode(); ptr = ptr->children[pos]; } // now at the end... ptr->terminate = true; } /** Returns if the word is in the trie. */ bool search(const string & word) { TrieNode * ptr = root; for (char c: word){ size_t pos = c - 'a'; if (ptr->children[pos] == nullptr) return false; ptr = ptr->children[pos]; } return ptr->terminate; } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { TrieNode * ptr = root; for (char c: prefix){ size_t pos = c - 'a'; if (ptr->children[pos] == nullptr) return false ptr = ptr->children[pos]; } return true; } private: TrieNode * root; }; /** * 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); */