Design a data structure that supports the following two operations:addWord(word)andsearch(word)
search(word)can search a literal word or a regular expression string containing only lettersa-zor..
A.means it can represent any one letter.
Notice
You may assume that all words are consist of lowercase letters a-z.
Have you met this question in a real interview?
Yes
Example
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") // return false
search("bad") // return true
search(".ad") // return true
search("b..") // return true
class WordDictionary {
public:
WordDictionary\(\) {
root = new TrieNode\(\);
}
// Adds a word into the data structure.
void addWord\(string word\) {
// Write your code here
auto node = root;
for \(int i = 0; i < word.size\(\); ++i\) {
if \(node->next\[word\[i\]-'a'\] == nullptr\) {
node->next\[word\[i\]-'a'\] = new TrieNode\(\);
}
node = node->next\[word\[i\]-'a'\];
}
node->isEnd = 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 searchHelper\(word, word.size\(\), 0, root\);
}
private:
struct TrieNode {
TrieNode\(\) {
isEnd = false;
for \(int i = 0; i < 26; ++i\) {
next\[i\] = nullptr;
}
}
TrieNode\* next\[26\];
bool isEnd;
};
TrieNode\* root;
bool searchHelper\(string& word, int len, int pos, TrieNode\* node\) {
if \(pos == len\) {
return node && node->isEnd;
}
if \(word\[pos\] == '.'\) {
for \(int i = 0; i < 26; ++i\) {
if \(node->next\[i\]\) {
if \(searchHelper\(word, len, pos+1, node->next\[i\]\)\) {
return true;
}
}
}
} else {
if \(node->next\[word\[pos\]-'a'\]\) {
return searchHelper\(word, len, pos+1, node->next\[word\[pos\]-'a'\]\);
} else {
return false;
}
}
return false;
}
};
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");