Word Search II
Table of Contents + −
You have a grid of letters and a list of words. Which of those words can you spell by walking the grid? This is the kind of question that looks easy with one word and turns scary with many. The trick is to search for all the words at once, and a trie is what makes that possible.
🎯 The Problem
You get a board of letters and a list of words. Return every word that can be built on the board.
- The board is a grid of letters.
- To build a word, start on any cell.
- Move up, down, left or right to a neighbor. Each move adds the next letter.
- You cannot reuse the same cell twice in one word.
Board: o a a n e t a e i h k r i f l v
Words: ["oath", "pea", "eat", "rain"]Output: ["oath", "eat"]“oath” walks o, then a path of neighbors, then t, then h. “eat” walks e, then a, then t. “pea” and “rain” cannot be formed, so they are left out.
Here is the board as a grid of cells. Each cell connects to its four neighbors, and a word is a path through connected cells.
🐢 Approach 1: Search Each Word Alone (Brute Force)
The idea in one line: take each word and run a separate board search for it.
The idea:
- For one word, try every cell as a start.
- From a start, do a depth-first search following neighbors that match the next letter.
- Depth-first search means you follow one path fully before backing up.
How it works:
- Repeat the whole board search once per word.
Why it is weak:
- If two words both start with “ea”, you redo that “ea” walk twice.
- The board walk is expensive, and you pay it again for every word.
- With many words this repeats a lot of work and gets slow.
Here is the search-each-word code:
def find_words(board, words): rows, cols = len(board), len(board[0])
def exists(word): def dfs(r, c, i, seen): if i == len(word): return True if r < 0 or c < 0 or r == rows or c == cols or (r, c) in seen or board[r][c] != word[i]: return False seen.add((r, c)) ok = dfs(r + 1, c, i + 1, seen) or dfs(r - 1, c, i + 1, seen) or dfs(r, c + 1, i + 1, seen) or dfs(r, c - 1, i + 1, seen) seen.remove((r, c)) return ok
return any(dfs(r, c, 0, set()) for r in range(rows) for c in range(cols))
return [word for word in words if exists(word)]⚡ Approach 2: Trie Plus DFS Backtracking (Best)
The idea in one line: put all words in a trie, then walk the board once and prune dead paths.
The idea:
- Put every word into a trie first. Words that share a prefix share one path.
- So you only walk a shared prefix once, not once per word.
How the board DFS works:
- Step on a cell and move down the trie by that letter at the same time.
- If the trie has no child for this letter, stop early. This is pruning, cutting a branch that cannot lead to an answer.
- When the trie node marks a word end, you found a word. Add it to the results.
Two details that matter:
- Mark a cell visited before going deeper, then unmark it after. This is backtracking, undoing your move when you come back.
- Clear the word end flag once you collect a word, so the same word is not added twice.
Here is the DFS at one cell. It moves into the trie child for that letter, then tries all four neighbors, then backtracks.
Steps to Solve
- Insert every word into a trie. Store the full word on the node where it ends.
- Start a DFS from every cell on the board.
- At each cell, look up its letter in the current trie node. If there is no child, stop this path.
- Move into that child. If the child holds a finished word, add it to the results and clear it so it is not added again.
- Mark the cell visited, then explore the four neighbors.
- Unmark the cell when you return, so other paths can use it again.
This Python version stores children in a dictionary and keeps the finished word on the node.
class TrieNode: def __init__(self): self.children = {} # letter -> child node self.word = None # full word if one ends here
def insert(root, word): cur = root for ch in word: if ch not in cur.children: cur.children[ch] = TrieNode() cur = cur.children[ch] cur.word = word # store finished word at the end node
def find_words(board, words): root = TrieNode() for w in words: insert(root, w)
rows, cols = len(board), len(board[0]) results = []
def dfs(r, c, node): if r < 0 or r >= rows or c < 0 or c >= cols: return ch = board[r][c] if ch == "#" or ch not in node.children: # used or pruned return nxt = node.children[ch] if nxt.word is not None: # a word ends here results.append(nxt.word) nxt.word = None # avoid duplicates board[r][c] = "#" # mark visited dfs(r + 1, c, nxt) dfs(r - 1, c, nxt) dfs(r, c + 1, nxt) dfs(r, c - 1, nxt) board[r][c] = ch # backtrack: restore
for r in range(rows): for c in range(cols): dfs(r, c, root) return results
board = [ ["o", "a", "a", "n"], ["e", "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"],]words = ["oath", "pea", "eat", "rain"]print(find_words(board, words))The output of the above code will be:
['oath', 'eat']Let us read the Python DFS line by line, because the pruning and backtracking both live there.
The first check if r < 0 or r >= rows or c < 0 or c >= cols: return keeps us on the board. Stepping off the grid is not a valid move, so we stop.
The line if ch == "#" or ch not in node.children does two jobs in one. The # part means this cell is already used in the current word, so we cannot reuse it. The ch not in node.children part is the pruning. If the trie has no child for this letter, no stored word continues this way, so we stop early. That single check is what makes the trie version fast.
nxt = node.children[ch] moves us down the trie by one letter. Then if nxt.word is not None checks whether a full word ends on this node. If yes, we append it and set nxt.word = None. Clearing it stops the same word from being added twice.
board[r][c] = "#" marks the cell used before we go deeper. The four dfs calls try each neighbor. Finally board[r][c] = ch restores the cell. This restore is the backtracking, and it lets a different path use this cell later.
⏱️ Time and Space Complexity
The brute force searches the board once per word, so its cost scales with the number of words times the board walk. The trie version walks the board once and prunes hard. Let the board have M cells and let L be the longest word. From each cell a DFS can branch in three new directions per step, up to length L. So the worst case is about M times 4 times 3 to the power L minus one. The trie itself costs space equal to the total letters across all words.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute force, one DFS per word | O(W * M * 4 * 3^(L-1)) | O(L) recursion |
| Trie plus DFS backtracking | O(M * 4 * 3^(L-1)) | O(total letters) |
Tip
The line that makes this question click is the pruning check. When the trie has no child for the current letter, you stop right there. Say that out loud in the interview. It shows you understand why a trie beats searching one word at a time.
🧩 Key Takeaways
- ✅ Put all words in a trie first, so shared prefixes are walked only once.
- ✅ Run a single DFS over the board and move down the trie in step with each cell.
- ✅ When the trie has no child for the current letter, stop early. That is pruning.
- ✅ Mark a cell used before going deeper, then restore it after. That is backtracking.
- ✅ Clear a word from its node once collected, so you never add it twice.
Check Your Knowledge
Test what you learned. Pick an answer for each question, then click Check.
- 1
Why do we put all the words into a trie before searching the board?
Why: A trie lets shared prefixes be searched once and lets us stop early when no word continues a path.
- 2
What does it mean to prune a path during the board DFS?
Why: If the trie has no child for the letter, no stored word continues here, so we stop that branch.
- 3
How do we avoid reusing the same cell within one word?
Why: We mark the cell before going deeper and restore it on return, which is backtracking.
- 4
Why do we set the node's word to null after collecting it?
Why: Clearing the stored word prevents the same word from being reported more than once.