Design Add and Search Words: Trie with Wildcards

You need to design a data structure that supports adding words and searching for them, where search queries can contain the wildcard character "." that matches any single letter. addWord("bad") inserts "bad" into the dictionary. search(".ad") returns True because "bad" (or "dad", "mad", etc.) could match.

This is LeetCode 211: Design Add and Search Words Data Structure, and it is one of the best problems for understanding how a trie combines with DFS. If you have already solved Implement Trie, this problem takes that foundation and adds exactly one twist: when the search hits a ".", it must branch into every child and try them all. That branching is what turns a simple trie walk into a backtracking search.

Why this problem matters

A regular trie search walks one path through the tree: follow the "b" child, then the "a" child, then the "d" child. It is O(m) where m is the word length. But a wildcard dot at any position means you do not know which child to follow. You have to try all of them.

This is a clean introduction to trie wildcard search. The same idea shows up in regex engines, autocomplete with partial input, and any system where you need pattern matching over a dictionary of strings. The add and search words problem isolates the core technique: when you hit a wildcard, recurse into every branch. When you hit a literal character, follow the single matching branch.

The trie wildcard search pattern also teaches you something deeper about when DFS and backtracking are necessary. Normal trie operations are iterative loops. The moment wildcards enter the picture, you need recursion because a single position in the query can expand into multiple parallel search paths.

The key insight

addWord is identical to a standard trie insert. Nothing changes there. The entire challenge lives in search.

When search encounters a normal character, it works exactly like a trie search: check if the current node has a child for that character, and follow it. When it encounters ".", it tries every child of the current node. If any branch eventually returns True, the whole search returns True.

That "try every child" step is DFS. You are exploring a tree of possibilities, and you stop as soon as one path succeeds. The "." character is where the search branches, and the literal characters are where it narrows back down to a single path.

Visual walkthrough

Let's trace through searching for ".ad" in a trie that contains "bad", "dad", and "mad". Watch how the dot forces the search to branch into every child of the root, then each branch continues with the literal characters "a" and "d".

The critical moment is Step 1. A regular trie search would look for a specific character at position 0. The wildcard "." means we do not know what that character is, so we try all of them. Each branch runs an independent DFS for the remaining characters "ad". As soon as the "b" branch finds "bad" and confirms it is a complete word, the search returns True without needing to check "d" or "m".

The full solution

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            # Matched all characters
            if i == len(word):
                return node.is_end

            ch = word[i]

            if ch == ".":
                # Wildcard: try every child
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            else:
                # Literal character: follow the single path
                if ch not in node.children:
                    return False
                return dfs(node.children[ch], i + 1)

        return dfs(self.root, 0)

Let's break this down.

addWord is a standard trie insert. Walk from the root, create any missing child nodes along the way, and mark the final node as end-of-word. This is identical to the insert method in Implement Trie. No changes needed.

search is where the wildcard logic lives. We define a recursive dfs(node, i) function that takes the current trie node and the current index into the search word.

The base case: if i == len(word), we have matched every character. Return node.is_end to check whether this path represents a complete word. This is important. If we inserted "bad" and search for "ba.", the DFS reaches the "a" node after matching all three characters. But the "a" node is not end-of-word, so we return False. We need to reach an actual end-of-word node.

For a literal character, check if the current node has a child for that character. If not, this path is a dead end, return False. If yes, recurse into that child with the next index.

For the wildcard ".", loop over every child of the current node and recurse. If any child's DFS returns True, short-circuit and return True. If none of them work, return False.

Complexity analysis

Let m be the length of the word being searched, and n be the number of nodes in the trie (roughly the total number of characters across all inserted words).

addWord is O(m) time and space, identical to a standard trie insert. Each character creates at most one new node.

search without wildcards is O(m). The DFS follows a single path through the trie, same as a normal trie search. The recursion stack is O(m) deep.

search with wildcards depends on how many dots are in the query. In the worst case, every character is a ".", and the DFS visits every node in the trie. That is O(n) where n is the total number of nodes. In practice, most queries have few wildcards, and literal characters quickly prune the search space.

Space for the trie itself is O(n), same as a standard trie. The recursion stack during search is O(m).

Edge cases

Before submitting, check these:

• No wildcards: search("bad") should behave like a normal trie search. Make sure your DFS handles the all-literal case correctly without unnecessary branching.
• All wildcards: search("...") should return True if any 3-letter word exists in the dictionary. The DFS explores the entire trie up to depth 3.
• Wildcard at the end: search("ba.") should match "bad", "bat", "ban", or any 3-letter word starting with "ba".
• Empty dictionary: search(".") should return False if no words have been added. The root has no children to branch into.
• Single character words: addWord("a"), then search(".") should return True. The dot matches "a".
• Word not found: search("bae") should return False if "bae" was never inserted, even if "bad" and "bat" exist.

The building blocks

This problem is built from two reusable pieces that CodeBricks drills independently:

1. Trie structure (character-by-character traversal)

The core trie pattern from Implement Trie:

node = self.root
for ch in word:
    if ch not in node.children:
        node.children[ch] = TrieNode()
    node = node.children[ch]
node.is_end = True

This is the addWord method, unchanged from a basic trie insert. You walk the tree one character at a time, creating nodes where they do not exist. The same traversal loop is the skeleton for every trie problem. In the search method, the loop becomes recursion because wildcards force branching, but the underlying idea is the same: move one character at a time, one node deeper.

2. DFS with branching on wildcards

The recursive search function that handles the "." character:

def dfs(node, i):
    if i == len(word):
        return node.is_end
    if word[i] == ".":
        for child in node.children.values():
            if dfs(child, i + 1):
                return True
        return False
    if word[i] not in node.children:
        return False
    return dfs(node.children[word[i]], i + 1)

This is a DFS backtracking pattern. The wildcard "." generates multiple choices (every child). The literal character narrows to one choice. The structure is similar to the backtracking template you see in Word Search and other explore-all-paths problems. The difference is that here the "tree" you are searching is the trie itself, and the "choices" come from the children dictionary.

Common mistakes

1. Returning True at the end of the word without checking is_end. If you return True whenever i == len(word), you will get false positives. Searching "ba" would match against "bad" because the path "b" -> "a" exists. You must check that the final node is marked as end-of-word.

2. Forgetting to short-circuit the wildcard loop. If you use any(dfs(child, i + 1) for child in ...), make sure it is a generator expression (not a list comprehension). A list comprehension evaluates all branches even after finding a match, which wastes time.

3. Using an iterative approach for search. Because wildcards can branch into multiple paths, an iterative loop with a single node variable does not work. You need recursion (or an explicit stack with backtracking). The DFS approach is the natural fit.

4. Not handling the case where the wildcard has no children. If the current node has zero children and the character is ".", the loop body never executes. Make sure you return False after the loop, not inside it.

When to use this pattern

Look for these signals:

• The problem involves searching a dictionary with wildcards or partial matches
• You need to match patterns against a set of stored strings
• The problem combines a trie with DFS or backtracking
• You need prefix matching plus some form of flexible character matching

Problems that use similar trie + DFS techniques:

• Word Search II (LeetCode 212): Trie plus grid backtracking to find all dictionary words in a grid
• Implement Trie (LeetCode 208): The foundation. Master this first.
• Word Break (LeetCode 139): Trie can replace the hash set for dictionary lookups during DP

From understanding to recall

You have read through the add and search words solution. You see how the standard trie insert stays unchanged and how the search method adds DFS branching on ".". But can you write the entire WordDictionary class from scratch, including the recursive search, in five minutes?

That is the real test. The solution has subtle details: the base case checks is_end (not just i == len(word)), the wildcard loop short-circuits on the first True, the literal branch returns False on a missing child. These are not conceptually hard, but they are the kind of details you fumble under pressure if you have not drilled them.

Spaced repetition closes that gap. You practice writing the trie insert and the wildcard DFS from memory at increasing intervals. After a few rounds, the pattern is automatic. You see a trie wildcard search problem and the code flows out without hesitation.

The trie structure and the DFS-with-branching pattern are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Implement Trie - The foundation. If you have not solved this one first, start there. Add and Search Words is a direct extension.
• Word Search - Grid backtracking that shares the same DFS explore-and-backtrack structure. The branching logic in Word Search (try four neighbors) is analogous to the wildcard branching here (try every child).

CodeBricks breaks the add and search words problem into its trie-structure and wildcard-DFS building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a trie wildcard search problem shows up in your interview, you do not think about it. You just write it.