Wildcard Search Strategy

When encountering '.', try all possible children:

function search(word):
    function dfs(node, i):
        if i == word.length:
            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(this.root, 0)

For normal characters, follow the single path. For '.', branch into all children.

Time complexity: $O(L)$ for addWord. For search, worst case is $O(26^M)$ where $M$ is the number of dots, but typically much better due to trie pruning.