Solutions

# For normal chars, we search iteratively as usual. For '.' we use DFS, on any child dfs(node, start_index)
# tries


# O(n) time, where n is the length of the word
#     the time complexity is still O(n) because there are at most two dots ('.') in the word, making the complexity O((26^2) * n). 
# O(n + t) space, where t is the number of trie nodes
class Node:

    def __init__(self, v: str):
        self.val = v
        self.children = [None] * 26
        self.is_end = False

    def contains_key(self, c: str) -> bool:
        return self.children[ord(c) - ord('a')] is not None

    def get_child(self, c: str) -> 'Node':
        return self.children[ord(c) - ord('a')]
    
    def set_child(self, c: str) -> None:
        self.children[ord(c) - ord('a')] = Node(c)


class WordDictionary:

    def __init__(self):
        self.root = Node('#')

    def addWord(self, word: str) -> None:
        curr = self.root
        for c in word:
            if not curr.get_child(c):
                curr.set_child(c)
            curr = curr.get_child(c)
        curr.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node: Node, start: int) -> bool:
            curr = node

            for i in range(start, len(word)):
                c = word[i]

                if c != '.':
                    if not curr.contains_key(c):
                        return False
                    curr = curr.get_child(c)
                else:
                    for child in curr.children:
                        if child and dfs(child, i + 1):
                            return True
                    return False
            return curr.is_end

        return dfs(self.root, 0)


# Brute force - O(n * m) search
class WordDictionaryBruteForce:

    def __init__(self):
        self.store = []

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

    def search(self, word: str) -> bool:
        for w in self.store:
            if len(w) != len(word):
                continue
            i = 0
            while i < len(w):
                if w[i] == word[i] or word[i] == '.':
                    i += 1
                else:
                    break
            if i == len(w):
                return True
        return False



from unittest import TestCase

class WorkDictionaryTest(TestCase):

    def test_worddict(self):
        wordDictionary = WordDictionary()
        wordDictionary.addWord("day");
        wordDictionary.addWord("bay");
        wordDictionary.addWord("may");
        self.assertFalse(wordDictionary.search("say"))
        self.assertTrue(wordDictionary.search("day"))
        self.assertTrue(wordDictionary.search(".ay"))
        self.assertTrue(wordDictionary.search("b.."))


if __name__ == '__main__':
    import unittest
    unittest.main()