LeetCode 79 · Backtracking · DFS · Matrix

Word Search

MediumTrace a word through a grid of letters using DFS with backtracking.
Given an m × n grid of characters and a word, return true if the word exists in the grid. The word is built from letters of sequentially adjacent cells (horizontally or vertically neighbouring); the same cell may not be used more than once in a single path.

Walkthrough

try:
Separate rows with spaces. Letters move up/down/left/right; each cell is used at most once per path.
word
ABCCED
A
B
C
E
S
F
C
S
A
D
E
E
currentpath so farmismatch
1
function exist(board, word) {
2
  const R = board.length, C = board[0].length;
3
  function dfs(r, c, i) {
4
    if (i === word.length) return true;
5
    if (r<0||c<0||r>=R||c>=C) return false;
6
    if (board[r][c] !== word[i]) return false;
7
    const tmp = board[r][c];
8
    board[r][c] = '#';            // mark used
9
    const found = dfs(r+1,c,i+1) || dfs(r-1,c,i+1)
10
                || dfs(r,c+1,i+1) || dfs(r,c-1,i+1);
11
    board[r][c] = tmp;           // backtrack
12
    return found;
13
  }
14
  for (let r = 0; r < R; r++)
◄
15
    for (let c = 0; c < C; c++)
16
      if (dfs(r, c, 0)) return true;
17
  return false;
18
}
step 0 / 34
line 14
Scan for a starting cell
Any cell could be the first letter, so try starting a DFS from each one until the word is found.

Intuition

Any cell could be the first letter, so try starting a depth-first search from every cell.

From a cell, the DFS matches word[i] here, then recurses into the four neighbours looking for word[i+1] — a classic “try a choice, recurse, undo” backtracking shape.

To stop a path from reusing a cell, temporarily overwrite it (e.g. with “#”) before recursing, then restore it afterwards. That restore is the backtrack.

A branch dies on three conditions: you run off the grid, the letter does not match, or the cell is already in the current path. If any neighbour reaches the end of the word, the answer is true.

The algorithm

  1. 01For each cell, start a DFS with index i = 0.
  2. 02In dfs(r, c, i): if i equals the word length, the whole word matched → true.
  3. 03Fail if out of bounds, or the cell does not equal word[i].
  4. 04Mark the cell used, recurse into all four neighbours for i + 1, then restore the cell (backtrack).
  5. 05Return true if any start cell’s DFS succeeds; otherwise false.

Reference implementation

1
function exist(board, word) {
2
  const R = board.length, C = board[0].length;
3
  function dfs(r, c, i) {
4
    if (i === word.length) return true;
5
    if (r < 0 || c < 0 || r >= R || c >= C) return false;
6
    if (board[r][c] !== word[i]) return false;
7
    const tmp = board[r][c];
8
    board[r][c] = '#';                        // mark used
9
    const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1)
10
               || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
11
    board[r][c] = tmp;                         // backtrack
12
    return found;
13
  }
14
  for (let r = 0; r < R; r++)
15
    for (let c = 0; c < C; c++)
16
      if (dfs(r, c, 0)) return true;
17
  return false;
18
}

Complexity

Time
O(m · n · 4^L) worst case, where L is the word length (each step branches into ~4 directions).
Space
O(L) for the recursion stack (plus in-place marking, no extra grid).