Wildcard and Grid Search with a Trie

A trie is more than a lookup table: it is a map that can guide a search. When the query has wildcards, a DFS over the trie tries every child at a .. When you search a grid of letters for many words at once, the trie tells you, cell by cell, whether any word still starts with the path you've walked. If the current path isn't in the trie, stop searching immediately.

The idea#

Both problems walk the trie side by side with something else: the pattern in one case, the grid in the other.

Wildcard search. Walk the pattern one character at a time. A normal letter follows exactly one child. A . matches any letter, so try every child and succeed if any branch succeeds. With no dots this is the usual $O(L)$ search. With all dots the worst case is often quoted as $O(26^L)$ , but the DFS can't visit more nodes than the trie holds, so the real cap is the trie's size.

Grid search (Boggle). Build one trie from all the words, then start a backtracking DFS from every cell. Move from the current trie node to the child for the next cell's letter. If that child doesn't exist, no word continues this way, so the whole branch is skipped. Store each word at its end node so you can report it the moment you reach it. One DFS searches for every word at the same time, instead of running a separate search per word.

Complexity of the grid search#

Grid search is the expensive one, so its cost is worth getting right. A first guess is $O(R \cdot C \cdot 4^L)$ , but that's too high. The first step from a cell has 4 directions; every later step has only 3, because you never step back onto the cell you came from.

Part	Cost	Notes
Build the trie	$O(K)$	$K$ = total length of all words
Search	$O(R \cdot C \cdot 3^L)$	a DFS from each of the $R \cdot C$ cells, depth at most $L$ (longest word)
Space	$O(K)$	the trie, plus $O(L)$ recursion

How to spot it#

These cues point to a trie-guided search.

A dictionary of words plus queries containing a wildcard such as ..
"Find all words from the list that appear in the grid."
Many words and a search space where each step extends a prefix.

Template#

Both shapes assume each node stores the full word at its end node, so a search can report it on arrival. The first block is the wildcard match.

matches(node, pattern, i):
    if i == len(pattern): return node holds a word
    if pattern[i] is a wildcard:       # try every branch
        return true if matches(child, pattern, i + 1) for any child
    child = node's child for pattern[i]
    return child exists and matches(child, pattern, i + 1)

Grid DFS guided by the trie#

The second shape is the grid search. Build one trie from all the words, then start this DFS from every cell whose letter is a child of the root.

dfs(cell, parent):
    node = parent's child for the cell's letter
    if node holds a word:
        record the word; clear it from node    # report each word once
    mark cell as visited on this path
    for each neighbor of cell (up, down, left, right):
        if neighbor is in the grid and unvisited
                and its letter is a child of node:
            dfs(neighbor, node)
    unmark cell                                # restore on backtrack
    if node has no children and no word:
        delete node from parent                # dead branch: prune

Two lines in that code keep it fast: remove a word once found, and prune trie branches that have nothing left.

Pitfalls#

These mistakes cause the most wrong answers.

Quoting $4^L$ . After the first step there are only 3 directions, so the bound is $O(R \cdot C \cdot 3^L)$ .
Reporting a word many times. The same word can be reachable from several paths. Clear the stored word when you record it, or collect into a set.
Not pruning. Without removing finished branches, the DFS keeps re-entering parts of the trie that can no longer produce a word, and large tests time out.
Forgetting to unmark the cell. The cell must be restored after the DFS returns, or other paths can't use it.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Design Add and Search Words Data Structure

addWord is a normal trie insert. search is the recursive wildcard match: a letter follows one child, and a . tries every child and succeeds if any branch does.

Hint: Word Search II

Build one trie of all the words and run the grid DFS from every cell. Overwrite the cell with a marker such as "#" while it is on the path, and restore it on the way back. Clear each word when you find it and delete empty branches, or large tests time out.

Hint: Word Search

There is only one word, so a trie adds nothing. Run the same backtracking DFS from each cell, but compare against the next letter of the word instead of a trie child.

Key takeaways#

A trie can steer a DFS: follow one child per letter, every child for a wildcard.
In a grid, stop the moment the path is not a prefix of any word.
Grid search is $O(R \cdot C \cdot 3^L)$ : 4 directions at the first step, then 3.
Remove found words and prune empty branches to keep the search fast.

Core idea#

A trie can guide a DFS. For a wildcard, try every child. For a grid of letters, the trie says whether any word still starts with the current path. If the path is not in the trie, stop at once.

Key points#

Wildcard: a letter follows one child. A . tries every child and succeeds if any branch does.
No dots: $O(L)$ . All dots: often quoted as $O(26^L)$ , but the trie's size is the real cap.
Grid (Word Search II): build one trie from all words. Start a backtracking DFS from every cell.
Move to the child for the next cell's letter. A missing child skips the whole branch.
Store each word at its end node and report it on arrival.
One DFS searches for every word at the same time.
Two speed-ups: clear a word once found, and delete trie branches with nothing left.

Complexity#

Part	Cost
Build the trie	$O(K)$ , total length of all words
Grid search	$O(R \cdot C \cdot 3^L)$
Space	$O(K)$ plus $O(L)$ recursion

Template#

dfs(cell, parent):
    node = parent's child for the cell's letter
    if node holds a word:
        record the word; clear it from node    # report each word once
    mark cell as visited on this path
    for each neighbor in the grid, unvisited,
            whose letter is a child of node:
        dfs(neighbor, node)
    unmark cell                                # restore on backtrack
    if node has no children and no word:
        delete node from parent                # prune a dead branch

Pitfalls#

Quoting $4^L$ . After the first step only 3 directions remain.
Reporting a word many times. Clear the stored word, or collect into a set.
No pruning. The DFS re-enters dead branches and large tests time out.
Forgetting to unmark the cell. Other paths then cannot use it.

Say it in an interview#

"One trie of all words lets a single DFS search for every word at once."
"The moment the path is not a prefix, stop that branch."