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

class WordDictionary:
    #SC: O(26**maxLen)
    #TC: adding: O(maxLen)
    #    searching: max: O(26**Len)


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

    def addWord(self, word: str) -> None:
        node = self.root
        for w in word:
            if w not in node.children:
                node.children[w] = trieNode()
            node = node.children[w]
        node.is_word = True


    def search(self, word: str) -> bool:
        return self.help(word, 0, self.root)

    def help(self, word, idx, node):
        if idx == len(word):
            return node.is_word

        if word[idx] != '.':
            if word[idx] not in node.children:
                return False
            else:
                return self.help(word, idx+1, node.children[word[idx]])
        else:
            for child in node.children:
                if self.help(word, idx+1, node.children[child]):
                    return True

            return False

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)