211. Design Add and Search Words Data Structure
# Medium
Key idea: very similar to #208, the only difference is search()
, must have a helper function to do backtracking, check one letter every time until done.
class WordNode {
public:
WordNode *child[26];
bool isEndOfWord;
WordNode(): isEndOfWord(false) {
for(auto &a : child) {
a = nullptr;
}
}
};
class WordDictionary {
public:
/** Initialize your data structure here. */
WordDictionary() {
root = new WordNode();
}
/** Adds a word into the data structure. */
void addWord(string word) {
WordNode *p = root;
for(auto &a : word) {
int i = a - 'a';
if(!p->child[i]) p->child[i] = new WordNode();
p = p->child[i];
}
p->isEndOfWord = true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
bool search(string word) {
return helper(word, 0, root);
}
private:
WordNode *root;
bool helper(string &word, int x, WordNode *p) {
// edge case
if(x == word.size()) return p->isEndOfWord;
// regular case
// is '.', backtracking
if(word[x] == '.') {
for(auto &a : p->child) {
// return helper(word, x+1, a);
if(a && helper(word, x+1, a)) return true;
}
return false;
}
// is letter
else {
return p->child[word[x] - 'a'] && helper(word, x+1, p->child[word[x] - 'a']);
}
}
};
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary* obj = new WordDictionary();
* obj->addWord(word);
* bool param_2 = obj->search(word);
*/
Last updated
Was this helpful?