Word Search II

Hard

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"]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.