## Add and Search Word - Data structure design

07/16/2016 Backtracking Trie Design

## Question

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")
search("b..") -> true


Note:

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

## Solution

Result: Accepted Time: 84 ms

Here should be some explanations.

struct Node{
bool exist;
Node * nodes[26]={0};
Node(const bool & e=false):exist(e){}
Node * & get_node(const char & a)
{
return nodes[a-'a'];
}
const Node * get_node(const char & a) const
{
return nodes[a-'a'];
}
};
class WordDictionary {
public:
Node root;
Node * tmp = &root;
for(const auto & c:word)
{
if(!tmp->get_node(c))
tmp->get_node(c) = new Node();
tmp= tmp->get_node(c);
}
tmp->exist = true;
}
bool srch(const Node * now,const char *ptr)
{
if(now == NULL || *ptr == '\0')
return now && now->exist;
if(*ptr!='.')
return srch(now->get_node(*ptr),ptr+1);
else
for(char c = 'a'; c <='z'; c++)
if(srch(now->get_node(c),ptr+1))
return true;
return false;
}

// 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 srch(&root,word.c_str());
}
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$