212. Word Search II

Given an m×n board of letters and a list of words, return every word that can be formed from sequentially adjacent (horizontal or vertical) cells, using each cell at most once per word.

Put all words in a trie and run one DFS from every cell, walking the board and the trie together. A path stops as soon as no word has it as a prefix; reaching a stored word records it once.

1function findWords(board: string[][], words: string[]): string[] {
2  const root: Trie = { kids: new Map(), word: null };
3  for (const w of words) {
4    let n = root;
5    for (const c of w) n = n.kids.get(c) ?? n.kids.set(c, { kids: new Map(), word: null }).get(c)!;
6    n.word = w;
7  }
8  const res: string[] = [], m = board.length, n = board[0].length;
9  const dfs = (r: number, c: number, node: Trie) => {
10    const ch = board[r]?.[c], next = ch && node.kids.get(ch);
11    if (!next) return;
12    if (next.word) { res.push(next.word); next.word = null; }
13    board[r][c] = "#";
14    dfs(r + 1, c, next); dfs(r - 1, c, next); dfs(r, c + 1, next); dfs(r, c - 1, next);
15    board[r][c] = ch;
16  };
17  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) dfs(r, c, root);
18  return res;
19}

words = oath, pea, eat, rain

board

o	a	a	n
e	t	a	e
i	h	k	r
i	f	l	v

found

empty

Insert 4 words into a trie.

1 / 0

Space: play/pause · ←/→: step