Word Search II asks you to find many words in a letter grid at once. The naive approach — run a separate grid search per word — explodes in cost. The fix is a classic interview combo: a trie to share work across all the words, plus a DFS with backtracking that the trie aggressively prunes.
Problem. Given an m x n grid of letters and a list of words, return every word from the list
that can be formed by a path of adjacent cells (up/down/left/right). A cell may not be reused within
a single word.
Example: grid
o a a
e t hwith words = ["oath", "eat"] → answer ["oath", "eat"].
The slow way first
The obvious idea: for each word, run a full grid DFS to see if that word exists. With W words and a grid of N cells, that is roughly O(W · N · 4^L) where L is the word length — you redo the same grid exploration once per word, re-walking shared prefixes over and over.
The question to ask: several words start with the same letters — can I search for all of them in a single walk? Yes. If I store the words in a structure that shares common prefixes, one DFS down the grid can chase every word simultaneously.
The idea: a trie guides (and prunes) the DFS
Insert all the words into a trie (prefix tree). Then DFS the grid, but carry a trie node alongside the grid cursor. At each cell, only continue if the cell letter is a child of the current trie node. If it is not, that whole branch is dead — stop immediately. When you land on a trie node marked as a word-end, you have spelled a real word: collect it.
The trie is what makes this fast: a path that cannot possibly spell any word is cut off after a single letter, instead of being explored to full depth.
Walk through it
Step through the animation. On the left is the trie for oath and eat; on the right is the grid with a dfs cursor. Watch the cursor follow trie edges: o → a → t → h spells "oath" and we collect it, then a fresh start on e walks e → a → t for "eat". Any neighbor whose letter is not a trie child never gets explored.
Pseudocode
build a trie from all words, marking the last node of each word as a word-end
found = empty list
define dfs(r, c, node):
if node is a word-end:
add that word to found (and unmark so we do not re-add it)
letter = grid[r][c]
if letter is not a child of node: # the prune
return
mark grid[r][c] as used
for each adjacent cell (nr, nc):
dfs(nr, nc, child node for letter)
unmark grid[r][c] # backtrack
for every cell (r, c) in the grid:
dfs(r, c, trie root)
return foundThe Python solution
def find_words(board, words):
trie = {}
for w in words:
node = trie
for ch in w:
node = node.setdefault(ch, {})
node["$"] = w # mark word end
found = []
def dfs(r, c, node):
if "$" in node:
found.append(node.pop("$"))
ch = board[r][c]
if ch not in node: # no trie child → prune
return
board[r][c] = "#" # mark used
for nr, nc in neighbors(r, c):
dfs(nr, nc, node[ch])
board[r][c] = ch # backtrack
for r in range(len(board)):
for c in range(len(board[0])):
dfs(r, c, trie)
return found- The trie is a plain nested dict: each letter maps to a child dict, and
"$"marks a word-end (storing the full word for easy collection). dfscarries the currentnode; when it sees"$", it appends the word andpops the marker so duplicates are not collected twice.- Line 12-13 is the prune: if the cell letter is not a key in the current trie node, this path cannot spell any word, so we return at once.
board[r][c] = "#"marks the cell used during this path; the final line restores it (backtracking) so other paths can reuse it.- The double loop launches a DFS from every cell as a possible word start.
Complexity
| Case | Time | Notes |
|---|---|---|
| Per-word grid search | O(W · N · 4^L) (moderate) | re-walks shared prefixes |
| Trie + DFS (this solution) | O(N · 4^L) (moderate) | one walk finds all words |
O(total letters in words) (moderate)The trie removes the W factor: shared prefixes are walked once, and dead branches are pruned after a single mismatched letter. The extra space holds the trie, sized by the total number of letters across all words.
When this pattern shows up
Whenever a problem matches many strings/prefixes against the same input — multi-word search, prefix autocomplete, replacing words by prefix — reach for a trie. Pairing it with DFS/backtracking lets one traversal chase every candidate at once instead of one search per word.
Remember to backtrack: restore each cell after exploring its neighbors, or a single path will block
cells from being reused by other words. And collect each word only once — popping the "$" marker (or
using a set) avoids returning duplicates.
Practice
During the DFS, the cursor is on a cell whose letter is not a child of the current trie node. What happens?
1. Why store the words in a trie instead of searching for each word separately?
2. What makes the trie prune the search?
3. Why does the code restore board[r][c] after the loop over neighbors?
4. How does the solution avoid collecting the same word twice?