Word Search II

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.

Example 1:

Input: board = [["c","a","t"],["o","w","n"],["r","d","s"]], words = ["cat","cow","own","rat","zoo"]
Output: ["cat","cow","own"]
Explanation: "cat", "cow", and "own" can be traced on the board with adjacent cells; "rat" and "zoo" cannot.

Example 2:

Input: board = [["p","q"],["r","s"]], words = ["pq","prs","ps","qr"]
Output: ["pq","prs"]

Example 3:

Input: board = [["m"]], words = ["m"]
Output: ["m"]

Constraints:

• 1 <= m, n <= 8
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 6
• board[i][j] and words[i] consist of lowercase English letters.
• All the strings of words are unique.

Solution Breakdown

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.