Word Search II
Problem
Given a letter grid and a list of words, return every word that can be spelled by a path of adjacent cells (up, down, left or right) without reusing a cell within one word.
Example 1
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"]
Test cases
Case 1
Input: [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], ["oath","pea","eat","rain"] Expected (any order): ["eat","oath"]
Case 2
Input: [["a","b"],["c","d"]], ["abcb"] Expected (any order): []
Case 3
Input: [["a"]], ["a","b"] Expected (any order): ["a"]
View solutionHide solution1 approach
1. Trie of words + one grid DFS
Time O(R·C·4·3^(L−1)) worst caseSpace O(total characters)
Running Word Search once per word repeats work. Build a trie, then DFS from each cell following only trie edges. Store the word at its end node, and clear it once found to avoid duplicates.
function findWords(board, words) { const root = {}; for (const w of words) { let node = root; for (const ch of w) node = node[ch] ??= {}; node.word = w; } const R = board.length, C = board[0].length, res = []; const dfs = (r, c, parent) => { const ch = board[r][c], node = parent[ch]; if (!node) return; if (node.word) { res.push(node.word); node.word = null; } board[r][c] = '#'; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nc >= 0 && nr < R && nc < C && board[nr][nc] !== '#') dfs(nr, nc, node); } board[r][c] = ch; }; for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) dfs(r, c, root); return res;}Optimisation: delete a trie leaf once its word is found, so dead branches stop being explored.