# 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")
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.
# 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):
"""
Initialize your data structure here.
"""
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[26];
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 head = 0;
int tail = 25;
if (word[index] != '.')
{
head = word[index] - 'a';
tail = head;
}
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. */
void addWord(string word) {
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();
* obj->addWord(word);
* bool param_2 = obj->search(word);
*/