hard

Word Search II

Find every word from a list that can be traced through a grid of letters.

1. Define the problem

Word Search II

Given an m x n board of characters and a list of words, return every word that can be traced by moving to horizontally or vertically adjacent cells, where the same cell is never reused within one word. For each word, try depth-first search from every cell that matches its first letter, following the letters of the word one step at a time and backtracking the moment a step fails or the word is confirmed.

Constraints

  • m == board.length
  • n == boardi.length
  • 1 ≤ m, n ≤ 12
  • boardi[j] is a lowercase English letter
  • 1 ≤ words.length ≤ 3 × 104
  • 1 ≤ wordsi.length ≤ 10

Example

Inputboard = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']], words = ['oath','pea','eat','rain']
Output['eat','oath']

Explanation 'oath' traces (0,0) → (0,1) → (1,1) → (2,1). 'eat' traces (1,3) → (1,2) → (1,1). Neither 'pea' nor 'rain' can be traced through adjacent cells.

2. Know the words first

In plain terms

Backtracking
Undoing the last move before trying a different one — here, un-marking a cell as visited once a path through it stops working out.
3. Visualize the solution

One cell per step of the path that spells 'oath' — four steps for four letters

One cell per step of the path that spells 'oath' — four steps for four letters
Statusdfs 'oath' from (0,0)

(0,0) = 'o' matches — step to a neighbor holding 'a'.

What happens in this step

dfs(index 0, expecting 'o', i=0)

index 0 = board[0][0] = 'o' — matches word[0] = 'o'
visited = {0}
try neighbors in order: down(index4)='e', up(oob), right(index1)='a', left(oob)

down fails ('e' ≠ 'a'), so the search steps right to index 1 next.
Step 1 of 4

Steps to visualize

  1. The row has four slots, one per letter of 'oath'. The label is the board cell the search is standing on, counted flat across the board (0-15).
  2. A slot shows — until the search actually steps onto that cell and matches the letter there.
  3. For a given word, try starting the search from every cell matching its first letter.
  4. At each step, only move to an adjacent cell holding the next letter that has not been used yet in this attempt.
  5. Reaching the end of the word with every letter matched means the word was found.
  6. If a path runs out of matching neighbors, undo the last cell and try a different direction.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per step of the path that spells 'oath' — four steps for four letters
Statusdfs 'oath' from (0,0)

(0,0) = 'o' matches — step to a neighbor holding 'a'.

What happens in this step

dfs(index 0, expecting 'o', i=0)

index 0 = board[0][0] = 'o' — matches word[0] = 'o'
visited = {0}
try neighbors in order: down(index4)='e', up(oob), right(index1)='a', left(oob)

down fails ('e' ≠ 'a'), so the search steps right to index 1 next.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function findWords(board, words) {
  const rows = board.length;
  const cols = board[0].length;

  function dfs(r, c, word, index, visited) {
    if (index === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;

    const key = r + ',' + c;
    if (visited.has(key)) return false;
    if (board[r][c] !== word[index]) return false;

    visited.add(key);
    const found =
      dfs(r + 1, c, word, index + 1, visited) ||
      dfs(r - 1, c, word, index + 1, visited) ||
      dfs(r, c + 1, word, index + 1, visited) ||
      dfs(r, c - 1, word, index + 1, visited);
    visited.delete(key);

    return found;
  }

  const found = new Set();

  for (const word of words) {
    let exists = false;
    for (let r = 0; r < rows && !exists; r++) {
      for (let c = 0; c < cols && !exists; c++) {
        if (dfs(r, c, word, 0, new Set())) exists = true;
      }
    }
    if (exists) found.add(word);
  }

  return Array.from(found).sort();
}
Time
O(words × rows × cols × 4^L) — L is a word's length
Space
O(L) — for the recursion stack and the visited set
6. Test cases

Test cases

InputExpectedCovers
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']], words = ['oath','pea','eat','rain']['eat','oath']example from the docstring
board = [['a']], words = ['a']['a']smallest valid board, single letter word
board = [['a','b'],['c','d']], words = ['xyz'][]none of the letters exist on the board
board = [['a','a']], words = ['aaa'][]a word cannot be formed by reusing the same cell twice
board = [['a','b'],['c','d']], words = ['ab','ac','bd','dc','ad']['ab','ac','bd','dc']several words checked at once, some found and one not, diagonal excluded
board = [['a','a','a'],['a','a','a'],['a','a','a']], words = ['aaaaaaaaa']['aaaaaaaaa']a long word that requires a winding path through every cell exactly once
board = [['a','b']], words = ['abc'][]a word needs more cells than the board has

Keep reading