208. Implement Trie (Prefix Tree)

struct TrieNode { TrieNode(): is_word(false), children(26, nullptr) {} ~TrieNode() { for (TrieNode * child : children){ if (child) delete child; // delete non-null children } } bool is_word; vector<TrieNode*> children; // use index of that vector to indicate character, thus do not need to store char explicitly }; class Trie { public: /** Initialize your data structure here. */ Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ void insert(const string & word) { TrieNode * ptr = root; for (char c: word){ size_t pos = c - 'a'; // find the position if (ptr->children[pos] == nullptr) ptr->children[pos] = new TrieNode(); ptr = ptr->children[pos]; } ptr->is_word = true; } /** Returns if the word is in the trie. */ bool search(string word) { if (root->children.empty()) return false; TrieNode * ptr = root; for (char c : word){ size_t pos = c - 'a'; if (ptr->children[pos] == nullptr) return false; else ptr = ptr->children[pos]; } return ptr->is_word; } /** 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; else 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); */