The problem
Given a grid of letters and a list of words, return every word that can be traced in the grid by moving up, down, left or right, without using the same cell twice in a word.
Input: board = oaan / etae / ihkr / iflv, words = [oath, pea, eat, rain] Output: ["oath", "eat"]
Picture it
Picture a word-search puzzle. Searching for each word separately repeats a lot of work. Instead we put all the words in a letter tree (trie). Then from each cell we walk the grid and the trie together: we only keep walking while the letters so far are the start of some word. The moment no word continues, we turn back.
How to recognise it
- You trace paths through a grid (up, down, left, right, no cell twice), which is backtracking: step into a cell, explore, then undo the step.
- There are many words to look for at once, and they share prefixes. Searching for each word separately repeats the same walks.
- A trie lets one walk check all words at the same time: the path so far must be a prefix of some word, or the walk can stop.
- The board is at most 12 × 12, but there can be 3 × 10^4 words of up to 10 letters.
Start with brute force
Run the single-word search (LeetCode 79) once for every word.
def exist(board, word):
R, C = len(board), len(board[0])
def dfs(r, c, k):
if k == len(word):
return True
if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[k]:
return False
board[r][c] = "#"
ok = any(dfs(r + dr, c + dc, k + 1)
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
board[r][c] = word[k]
return ok
return any(dfs(r, c, 0) for r in range(R) for c in range(C))
def find_words_brute(board, words):
return [w for w in words if exist(board, w)]
One word costs up to O(R · C · 4 · 3^(L − 1)): every start cell, then at most three new directions per step. With 3 × 10^4 words that is already 3 × 10^4 × 144 ≈ 4.3 × 10^6 starting walks, and on a board full of a with words like aaaaaaaaab each walk explores thousands of paths.
From brute force to the idea
- Find the waste. Words such as
oath,oatandoatsall start with the same walko,a,t, but the brute force repeats it for each word. - Put the words in a trie.
build_triestores each word along its letters and puts the whole word under the"$"key at its end, so a match can be reported without rebuilding the string. - Walk the board and the trie together.
dfs(r, c, node)steps into a cell only if its letter is a child of the current trie node. If not, no word continues this way: a dead end. - Report and remove. When the new node has
"$", a word is complete.node.pop("$")appends it and deletes the marker, so the same word is never reported twice even if the board spells it along several paths. - Mark cells in use. Set the cell to
"#"before exploring neighbours (nbrsyields the in-grid ones) and restore the letter afterwards."#"is never a trie key, so a used cell cannot be stepped into again in the same path. - Start everywhere.
all_cellslists every position, and each starts a walk from the root.
This is the key idea: one DFS per start cell follows the trie, so all words with a shared prefix share the work, and a path stops as soon as it is no word's prefix.
The key idea
Build a trie of all words and run one backtracking search over the grid, pruned by the trie.
Python solution
def find_words(board, words):
trie = build_trie(words) # "$" = end
found = []
def dfs(r, c, node):
ch = board[r][c]
if ch not in node:
return # dead end
node = node[ch]
if "$" in node:
found.append(node.pop("$"))
board[r][c] = "#" # in use
for nr, nc in nbrs(board, r, c):
if board[nr][nc] != "#":
dfs(nr, nc, node)
board[r][c] = ch
for r, c in all_cells(board):
dfs(r, c, trie)
return found
def build_trie(words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["$"] = w
return root
def all_cells(g):
return [(r, c) for r in range(len(g))
for c in range(len(g[0]))]
def nbrs(g, r, c): # in-grid neighbours
R, C = len(g), len(g[0])
for nr, nc in ((r+1, c), (r-1, c),
(r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, ncIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
Let L be the longest word length (at most 10) and S the total letters in all words.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(W · R · C · 4 · 3^(L − 1)) for W words: a full grid search per word | O(L) recursion depth |
| Trie + DFS (shown code) | O(S) to build the trie, plus O(R · C · 4 · 3^(L − 1)) for the walks, independent of W | O(S) for the trie, O(L) recursion depth |
Edge cases
- The example: returns
["oath", "eat"]. The order is the order of discovery, not the order ofwords. - Spelled more than once (board
a a, wordsa): returned once, because the marker is popped. - Reusing a cell (board
a b, wordaba): not found, since theais marked"#"while in use. - A 1 × 1 board:
ais found,aais not. - The board is changed during the search but every cell is restored, so the caller's board is the same afterwards.
- No pruning of finished branches: after
oathis found, its now-empty trie nodes stay, so later walks still step througho,a,t,h. Deleting empty child nodes on the way back is a common speed-up; the answer is correct without it.
Common mistakes
- Appending
node["$"]without popping it. The boarda awith wordathen returns["a", "a"]. - Forgetting to restore
board[r][c] = ch, so later walks see"#"and miss words. - Running a separate grid search for each word, which repeats the shared-prefix walks.
Now a word may also continue diagonally, so each cell has up to 8 neighbours. Cells still cannot be reused within a word. Describe your approach, then write it if you like.
Compare with our answer
Nothing about the trie changes. Only the neighbour generator does: yield all eight offsets instead of four. The "#" marking still stops a path from reusing a cell.
DIRS8 = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if dr or dc]
def nbrs(g, r, c): # in-grid neighbours, diagonals included
R, C = len(g), len(g[0])
for dr, dc in DIRS8:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
Replace the shown nbrs with this. Each step now has up to 7 unused directions instead of 3, so the worst case grows to O(R · C · 8 · 7^(L − 1)), but the trie still cuts most paths short.
A strong answer mentions: that only the neighbour list changes, that cells must still be marked in use, and how the branching factor grows.
1. A Boggle app must find which of 200,000 dictionary words appear on a 4 × 4 board. Which approach fits best?
The trie lets one walk check all words at once and stops a path as soon as it is no word's prefix. Per-word searches repeat the same walks 200,000 times, and generating every path without pruning explores far more than needed.
2. Why does the shown code's walk cost not grow with the number of words?
The DFS explores board paths, and at each step a single trie lookup checks every word with that prefix. More words make the trie bigger, but the number of board paths is bounded by the board and the longest word.
3. A learner writes found.append(node["$"]) instead of popping the marker. Which call now returns a wrong result?
a can be spelled from either cell, so without removing the marker it is appended twice. In the other boards each word can be traced along exactly one path, so the bug stays hidden.
Score 60% or more and the lesson is marked complete.