Word Search II Solution

Problem

You have a 2D grid of letters and a list of target words. Find every word from the list that can be spelled by tracing a path through adjacent cells — horizontally or vertically, never visiting the same cell twice within a single word. Return all matching words in any order.

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
Explanation: "eat" traces cells (1,3)→(1,2)→(1,1) and "oath" traces (0,0)→(0,1)→(1,1)→(2,1); "pea" and "rain" cannot be formed on this board.

Intuition

Running a separate DFS for each word forces you to re-traverse the same board paths whenever words share a prefix — "eat" and "earn" both walk through 'e'→'a' from the same starting cell. Building a Trie from all words first lets you sweep the board once: at each cell you descend both the grid and the Trie at the same time, discovering every matching word in a single pass.

Approach 1 — Brute Force DFS Per Word

Treat this as Word Search I repeated W times: for each word, try every cell as a starting point and backtrack through the grid.

For each word, scan every cell as a potential first character.
If the cell matches the first character, enter recursive DFS.
Mark the current cell '#' to block it from being reused within this path.
Recurse into all four neighbors, advancing the match index by one.
Restore the cell before returning so other words — and other paths — can use it.
Stop as soon as the word is found; move to the next word.

1def findWords(board: list[list[str]], words: list[str]) -> list[str]:
2    rows, cols = len(board), len(board[0])
3    found = []
4
5    def dfs(row: int, col: int, word: str, index: int) -> bool:
6        if index == len(word):
7            return True
8        if row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] != word[index]:
9            return False
10
11        temp, board[row][col] = board[row][col], '#'  # block this cell for the current path
12        matched = (dfs(row + 1, col, word, index + 1) or
13                   dfs(row - 1, col, word, index + 1) or
14                   dfs(row, col + 1, word, index + 1) or
15                   dfs(row, col - 1, word, index + 1))
16        board[row][col] = temp  # restore so other words can use this cell
17        return matched
18
19    for word in words:
20        for start_row in range(rows):
21            for start_col in range(cols):
22                if dfs(start_row, start_col, word, 0):
23                    found.append(word)
24                    break
25            else:
26                continue
27            break
28
29    return found

Time: O(W × M × N × 4 × 3^(L−1)) — each of W words triggers a full grid scan; from each start cell the DFS fans out 4 ways initially and 3 ways per step down to depth L (max word length).
Space: O(L) — the recursion stack reaches at most one word-length deep.

Approach 2 — Trie + Single DFS Pass

Insert all words into a Trie once, then sweep the board a single time with DFS descending both the grid and the Trie simultaneously.

Insert every word into a Trie; store the complete word string at its terminal node.
For each starting cell, call DFS with the Trie root.
At each DFS step, check whether the current board character exists as a child in the current Trie node — prune immediately if not.
When the Trie node holds a word string, record it and clear the field to prevent the same word appearing twice.
Mark the cell visited with '#', recurse into all valid neighbors, then restore the cell.
After backtracking, delete the Trie child node if it became empty — this stops future DFS calls from entering dead branches.

1def findWords(board: list[list[str]], words: list[str]) -> list[str]:
2    rows, cols = len(board), len(board[0])
3
4    # Nested dicts form the trie; '$' maps to the completed word string
5    trie: dict = {}
6    for word in words:
7        node = trie
8        for char in word:
9            node = node.setdefault(char, {})
10        node['$'] = word
11
12    found: list[str] = []
13
14    def dfs(row: int, col: int, node: dict) -> None:
15        char = board[row][col]
16        if char not in node:
17            return
18
19        next_node = node[char]
20        if '$' in next_node:
21            found.append(next_node.pop('$'))  # pop removes the marker so this word is never added twice
22
23        board[row][col] = '#'  # block this cell for the current path
24        for delta_row, delta_col in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
25            next_row, next_col = row + delta_row, col + delta_col
26            if 0 <= next_row < rows and 0 <= next_col < cols:
27                dfs(next_row, next_col, next_node)
28        board[row][col] = char  # restore so other starting cells can use this cell
29
30        if not next_node:  # prune this trie branch — no words remain beneath it
31            del node[char]
32
33    for start_row in range(rows):
34        for start_col in range(cols):
35            dfs(start_row, start_col, trie)
36
37    return found

Time: O(M × N × 4 × 3^(L−1) + W × L) — one DFS sweep over the grid with Trie-guided pruning, plus O(W × L) to build the Trie; the W multiplier on DFS work from Approach 1 is eliminated.
Space: O(W × L) — the Trie stores all word characters; the recursion stack is still O(L) deep.

Complexity Summary

Approach	Time	Space	When to use
Brute Force DFS Per Word	O(W × M × N × 4 × 3^(L−1))	O(L)	Tiny word list (1–2 words) where Trie construction isn't worth it
Trie + Single DFS Pass	O(M × N × 4 × 3^(L−1) + W × L)	O(W × L)	Any real word list — eliminates the W multiplier on DFS work

Common Mistakes

Not clearing the word marker after the first match — the same word can be reached via different starting cells and different paths; if you don't null out node.word the moment it's first found, you'll add it to results multiple times.
Forgetting to restore the board cell on backtrack — board[row][col] = '#' must be undone before the function returns; if skipped, that cell stays permanently blocked and every later starting cell will produce wrong results.
Skipping Trie branch pruning — once all words in a subtree have been collected, the DFS still descends into it on every future starting cell; deleting childless nodes on the way back eliminates this wasted work entirely.
Checking board[row][col] before validating bounds — accessing an out-of-range index before confirming the row and column are valid causes a runtime error; always check bounds first.
Running Word Search I in a loop for a large word list — the extra W multiplier on DFS time is the dominant cost for non-trivial inputs; the Trie removes it and is the intended solution.

Word Search II — Solution