leetcode – Add Search Word – Data structure design in cpp

leetcode – Add Search Word – Data structure design in cpp

Question Solution

leetcode – Add Search Word – Data structure design in cpp

Design a data structure that supports the following two operations:

void addWord(word)

bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord(“bad”)

addWord(“dad”)

addWord(“mad”)

search(“pad”) -> false

search(“bad”) -> true

search(“.ad”) -> true

search(“b..”) -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

Following is the class implementing a trie data structure.
class TrieNode{
public:
char c;
unordered_map<char, TrieNode*> children ;
bool isLeaf;
TrieNode(char c){
this->c = c;
}
TrieNode() : isLeaf(false), children() { }
};
class WordDictionary {
private :
TrieNode* root;
public:
WordDictionary(){
root = new TrieNode();
}
// Adds a word into the data structure.
void addWord(string word) {
TrieNode* child=root;
for(int i=0; i<word.length(); i++){
char c = word[i];
if(child->children.count(c)==0)
child->children[c]=new TrieNode();
child =child->children[c];
}
child->isLeaf = 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 dfsSearch(root->children, word, 0);
}
bool dfsSearch(unordered_map<char, TrieNode*>children, string word, int start) {
if(start == word.length()){
if(children.size()==0)
return true;
else
return false;
}
char c = word[start];
if(children.find(c) != children.end()){
if(start == word.length()-1 && children[c]->isLeaf){
return true;
}
return dfsSearch(children[c]->children, word, start+1);
}else if(c == ‘.’){
bool result = false;
unordered_map<char, TrieNode*>::iterator itr=children.begin();
for(; itr!= children.end();itr++){
if(start == word.length()-1 && (*itr).second->isLeaf){
return true;
}

//if any path is true, set result to be true;
if(dfsSearch((*itr).second->children, word, start+1)){
result = true;
}
}
return result;
}else{
return false;
}
}
};