# LeetCode 211. Design Add and Search Words Data Structure

## Description

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the `WordDictionary` class:

• `WordDictionary()` Initializes the object.
• `void addWord(word)` Adds `word` to the data structure, it can be matched later.
• `bool search(word)` Returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `'.'` where dots can be matched with any letter.

Example:

```Input
Output
```

[null,null,null,null,false,true,true,true]

Constraints:

• `1 <= word.length <= 500`
• `word` in `addWord` consists lower-case English letters.
• `word` in `search` consist of  `'.'` or lower-case English letters.
• At most `50000` calls will be made to `addWord` and `search`.

## Explanation

Create a trie to search and store words. When the word contains ‘.’, search recursively to check if next character matches.

## Python Solution

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

class WordDictionary:

def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()

def addWord(self, word: str) -> None:

node = self.root

for c in word:
if c in node.children:
node = node.children[c]
else:
node.children[c] = TrieNode()
node = node.children[c]

node.is_word = True

def search(self, word: str) -> bool:
if not word:
return False

return self.search_helper(self.root, word, 0)

def search_helper(self, node, word, index):
if not node:
return False

if index >= len(word):
return node.is_word

char = word[index]

if char != '.':

return self.search_helper(node.children.get(char), word, index + 1)

else:
for child in node.children:
if self.search_helper(node.children[child], word, index + 1):
return True

return False

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()