/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * bool param_2 = obj.search(word); */ classWordDictionary { private: classTrieNode { public: bool isWord = false; TrieNode* children[26] = {nullptr}; }; TrieNode* root = new TrieNode(); public: /** Initialize your data structure here. */ WordDictionary() = default;
/** Adds a word into the data structure. */ voidaddWord(string word){ TrieNode* run = root; for(char c : word) { if(nullptr == run->children[c - 'a']) run->children[c - 'a'] = new TrieNode(); run = run->children[c - 'a']; } run->isWord = true; }
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */ boolsearch(string word){ return query(std::move(word), root); } boolquery(string word, TrieNode* run, int index = 0){ for(int i = index; word[i]; i++) { if(nullptr != run && word[i] != '.') run = run->children[word[i] - 'a']; elseif(nullptr != run && word[i] == '.') { TrieNode* tmp = run; for(char c = 'a'; c <= 'z'; c++) { word[i] = c; run = tmp->children[word[i] - 'a']; if(query(word, run, i+1)) returntrue; } } elsebreak; } return run && run->isWord; } };