When encountering '.', try all possible children:
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.isEnd
c = word[i]
if c == '.':
for child in node.children.values():
if dfs(child, i + 1):
return True
return False
else:
if c not in node.children:
return False
return dfs(node.children[c], i + 1)
return dfs(self.root, 0)
For normal characters, follow the single path. For '.', branch into all children.
Time complexity: for addWord. For search, worst case is where is the number of dots, but typically much better due to trie pruning.