[link](https://leetcode.com/problems/design-add-and-search-words-data-structure/)

---

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 1:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

#### Constraints:

- 1 <= word.length <= 25
- word in addWord consists of lowercase English letters.
- word in search consist of '.' or lowercase English letters.
- There will be at most 2 dots in word for search queries.
- At most 104 calls will be made to addWord and search.

---

TrieNode: This is a helper class representing a node in the trie.

WordDictionary: The class is initialized with a root node for the trie.

addWord: This method is used to add a word to the word dictionary. It follows the same logic as the insert method in the previous trie implementation. It iterates over each character of the word and creates new nodes if necessary. The last node representing the word is marked as a word by setting the word attribute to True.

search: This method is used to search for a word in the word dictionary. It uses a helper function dfs (depth-first search) that takes the index j to start searching the word and the current node root. The dfs function performs a depth-first search on the trie to find a matching word or wildcard pattern.

dfs: The dfs function starts from the index j of the word and the current node root. It iterates over each character of the word, starting from j. If the character is a dot '.', it means it can match any character. In this case, it recursively searches all possible children of the current node. If any of the recursive calls returns True, it means there is a match, and the function returns True. Otherwise, it returns False.

If the current character is not a dot '.', the function checks if the character is present in the children dictionary of the current node. If not, it means there is no matching word, and the function returns False. Otherwise, it updates the current node to the child node corresponding to the character and continues the search.

If the function reaches the end of the word and the current node's word attribute is True, it means there is an exact match for the word, and the function returns True.

#### Solution 1

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

class WordDictionary:

    def __init__(self):
        self.root = TrieNode()
        

    def addWord(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.word = True
        

    def search(self, word: str) -> bool:
        def dfs(j, root):
            curr = root
            for i in range(j, len(word)):
                c = word[i]
                if c == '.':
                    for child in curr.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if c not in curr.children:
                        return False
                    curr = curr.children[c]
            return curr.word
        return dfs(0, self.root)
    

O(T): O(m)
O(S): O(n)