Coding Prep
Word Search II
Find all target words on a character board by combining trie pruning with backtracking DFS - one pass checks all words simultaneously.
Problem
Search indexing and word game solvers must find every word from a dictionary that can be formed on a character grid by walking adjacent cells (up, down, left, right) without reusing the same cell in one path. Given an m x n board and a list of target words, return all words that can be found on the board.
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]
→ ["eat","oath"]Solution
Approach: Build a trie of all target words, then run one trie-guided backtracking DFS over the board.
Insert every target word into a trie, but instead of an is_end flag store the full string at the terminal node (node.word = word) - on discovery you read it directly rather than reconstructing it from board positions, which are coordinates, not characters. Then launch dfs(trie.root, row, col) from every cell, since any cell can start a word. Inside the DFS, the board character and the trie advance in lockstep: if board[row][col] has no matching trie child, the entire branch is pruned immediately - that single check is what lets one pass cover all words at once, abandoning a path the moment no word uses it. Otherwise descend to next_node; if next_node.word is set, a complete word ends here, so append it to found and set next_node.word = None to avoid reporting it twice when another board path reaches the same node. Before recursing into the four neighbors, mark the cell visited with board[row][col] = '#' (a sentinel absent from every trie, so it auto-prunes), and restore the original character after all four calls return so other paths can reuse the cell. Recursion always advances to next_node, never node, because one character has been consumed.
Edge cases: A board path cannot reuse a cell within one word - the '#' sentinel guarantees this since '#' is never a trie edge. Words not on the board are simply never collected. Nulling node.word after collection dedupes multiple board routes to the same word.
Complexity: O(sum of word lengths) to build the trie; DFS is O(rows * cols * 4^L) worst case where L is the longest word, though trie pruning cuts this sharply in practice. O(total trie characters) space plus O(L) recursion depth.
Done reading? Mark it so it sticks in your dashboard.