212. Word Search II

212

HardTrie and Advanced String SearchTrie plus backtracking DFSTrie-guided grid DFS

Word Search II

Given an m x n board of characters and a list of words, return all words from the list that can be formed by a path of horizontally or vertically adjacent cells, where each cell may be used at most once per word.

Open official problem prompt ↗

In plain English

Find which dictionary words appear as adjacency-connected paths in the grid, doing it efficiently for a large word list.

Picture it like this

A word-search puzzle where, instead of hunting each word separately, you carry one master index (the trie) so a single sweep of the grid checks every word's prefix at once.

Example

Input: 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"]
Why: "oath" and "eat" each trace a connected path of adjacent cells; "pea" and "rain" cannot be traced.

Constraints

m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j] is a lowercase English letter1 <= words.length <= 3 * 10^41 <= words[i].length <= 10All words[i] are unique

Pattern lesson

See the pattern, then code

Trie-guided grid DFS

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. If the path built so far is not a prefix of any word, the trie has no matching child and the branch is pruned instantly, so the grid walk only follows letters that could still complete some word.

New words, made simpleKnow these before the algorithm

Trie: A tree where each root-to-node path spells a prefix; shared prefixes share nodes.
Backtracking: Marking a cell used, recursing, then unmarking so other paths can reuse it.
Prefix pruning: Abandoning a path the moment it stops matching any word's prefix.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

DFS per word

Re-scans the grid W times and shares nothing between words with common prefixes.

For each word, run a full grid DFS looking for that exact word.

Time O(W * M * N * 4^L)Space O(L)

Best choiceTrie-guided DFS

One sweep handles all words and prunes instantly on non-prefixes.

Build one trie of all words and DFS the grid once, following trie children.

Time O(M * N * 4 * 3^(L-1))Space O(sum of word lengths)

The rule we keep true

Invariant

The trie node passed into each DFS call always corresponds exactly to the string spelled by the cells on the current path.

Why this is correct

Reasoning

A word is reported only when the path reaches a node flagged as a complete word, and that node is reachable only by spelling the word letter-by-letter along adjacent unused cells, which is exactly the problem's definition of a match.

The algorithm in three movesSay these aloud before coding

1Insert every word into a trie, storing the full word at its terminal node

trie root -> o -> a -> t -> h ($=oath)

2DFS from each cell, descending into the trie child that matches the cell letter

path (0,0)->(0,1)->(1,1)->(2,1)

3When a node marks a complete word, record it and clear the marker to avoid duplicates

res = ['oath']

4Mark cells visited during the path and restore them on backtrack

5Prune dead trie leaves to shrink future searches

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readcell 'o'

2 · AskDoes root have child 'o'?

3 · Update statepath='o'

4 · ResultDescend; continue

Key takeaway

The cells o,a,t,h spell the word 'oath' along a connected adjacent path.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-8Build the trie
Each word becomes a root-to-leaf path; the terminal node stores the whole word under key '$'.
2
Lines 12-27DFS with trie
Only recurse into a neighbor if the current trie node has a child for its letter; pop '$' once found to dedupe.
3
Lines 28-30Leaf pruning
Removing exhausted trie branches keeps later searches from revisiting dead ends.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A word equal to a single cell
Duplicate words already deduped by problem constraints
Words sharing long common prefixes
A word that is a prefix of another word

Common beginner mistakes

Reporting the same word twice when it appears via multiple paths (fixed by popping the '$' marker)
Forgetting to restore the cell after recursion, corrupting other paths
Running a separate DFS per word and timing out
Using a visited set that is not reset between starting cells

Check your understanding

Why store the full word at the terminal node instead of just a boolean flag?

PyPython 3 · solution.py

Optimal

1class Solution:2    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:3        trie = {}4        for w in words:5            node = trie6            for ch in w:7                node = node.setdefault(ch, {})8            node['$'] = w9        rows, cols = len(board), len(board[0])10        res = []1112        def dfs(r, c, node):13            ch = board[r][c]14            if ch not in node:15                return16            nxt = node[ch]17            word = nxt.pop('$', None)18            if word is not None:19                res.append(word)20            board[r][c] = '#'21            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):22                nr, nc = r + dr, c + dc23                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':24                    dfs(nr, nc, nxt)25            board[r][c] = ch26            if not nxt:27                node.pop(ch, None)2829        for r in range(rows):30            for c in range(cols):31                dfs(r, c, trie)32        return res

Time complexityO(M * N * 4 * 3^(L-1)) where L is max word lengthOptimized

Space complexityO(total characters in words) for the trieExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftGoogleUber

Word Search II

Word Search II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search