## # 211. Add and Search Word - Data structure design

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.
``````

Example:

``````addWord("bad")
search("b..") -> true
``````

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

### # Solution

Approach 1: use a trie.

### # Code (Python)

Approach 1:

``````class TrieNode:
def __init__(self):
self.is_word = False
self.children = {}

class WordDictionary:

def __init__(self):
"""
"""
self._trie = TrieNode()

def addWord(self, word: 'str') -> 'None':
"""
Adds a word into the data structure.
"""
node = self._trie
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_word = True

def search(self, word: 'str') -> 'bool':
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
"""
return self._search(0, word, self._trie)

def _search(self, index, word, node):
if index == len(word):
return node.is_word
char = word[index]
if char != '.':
if char not in node.children:
return False
return self._search(index + 1, word, node.children[char])
else:
for child_node in node.children.values():
if self._search(index + 1, word, child_node) == True:
return True
return False
``````

### # Code (C++)

Approach 1:

``````class WordDictionary {
private:
struct TrieNode {
TrieNode *children;
bool isEnd;
TrieNode() {
for (int i = 0; i < 26; ++i)
{
children[i] = NULL;
}
isEnd = false;
}
};

TrieNode *root;

bool doSearch(string word, int index, TrieNode *start) {
if (start == NULL)
return false;
if (index == word.size())
return start->isEnd;
TrieNode *curr = start;
int tail = 25;
if (word[index] != '.')
{
}
for (int j = head; j <= tail; ++j)
{
if (doSearch(word, index+1, curr->children[j]))
return true;
}
return false;
}

public:
/** Initialize your data structure here. */
WordDictionary() {
root = new TrieNode();
}

/** Adds a word into the data structure. */
TrieNode *curr = root;
for (int i = 0; i < word.size(); ++i)
{
int j = word[i] - 'a';
if (curr->children[j] == NULL)
curr->children[j] = new TrieNode();
curr = curr->children[j];
}
curr->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 doSearch(word, 0, root);
}
};

/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary* obj = new WordDictionary();