Design Add & Search Words

Signal

Same "shared-prefix tree" shape as a plain trie, but a wildcard character that can match anything breaks the simple one-child-lookup walk — a wildcard forces you to branch and try every child at that position. Whenever a search needs to explore multiple possibilities at a single step, that's DFS/backtracking laid on top of the trie, not a plain walk.

Approach

Store words in a standard trie (insert is unchanged). For search, recurse character by character: on a normal letter, follow the single matching child if it exists, or fail; on ., try every child at that node and recurse into each, succeeding if any branch succeeds. Success at the end of the pattern requires landing on a node marked as a word end.

Skeleton

def dfs(node, i):
    if i == len(word): return node.is_end
    ch = word[i]
    if ch == '.':
        return any(dfs(child, i + 1) for child in node.children.values())
    return ch in node.children and dfs(node.children[ch], i + 1)

Solution

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def add_word(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node: TrieNode, i: int) -> bool:
            if i == len(word):
                return node.is_end
            ch = word[i]
            if ch == '.':
                return any(dfs(child, i + 1) for child in node.children.values())
            child = node.children.get(ch)
            return child is not None and dfs(child, i + 1)

        return dfs(self.root, 0)

Complexity

O(L) time for a pattern with no wildcards; up to O(26^k · L) in the worst case with k wildcards, since each wildcard can branch into every child. O(L) recursion depth, O(total characters) space for the trie itself.

Pitfalls

• Forgetting that a . at the very last position still needs node.is_end checked on whichever child branch is tried — the wildcard only replaces the character match, not the end-of-word requirement.
• Treating . as "skip this position" instead of "match exactly one character" — a wildcard must still consume one position in word, it doesn't let the pattern and the stored word have different lengths.
• Worst-case blowup with patterns like "....." (all wildcards) against a dense trie — worth naming the complexity honestly if asked about scaling, rather than implying this is always O(L).