LeetCode 211 Design Add and Search Words - Implementation

Trie with DFS for wildcard search.

class WordDictionary: def init(self): self.root = {}

def addWord(self, word):
    node = self.root
    for char in word:
        if char not in node:
            node[char] = {}
        node = node[char]
    node['$'] = True

def search(self, word):
    def dfs(node, i):
        if i == len(word):
            return '$' in node
        if word[i] == '.':
            for child in node:
                if child != '$' and dfs(node[child], i + 1):
                    return True
            return False
        if word[i] not in node:
            return False
        return dfs(node[word[i]], i + 1)
    return dfs(self.root, 0)

$O(m)$ add, $O(m)$ to $O(26^w \cdot m)$ search.