LeetCode 79 · Medium · Backtracking

Word Search

Given a grid of letters and a word, decide whether the word can be traced through the grid by stepping between horizontally or vertically adjacent cells, without using any cell twice.

O(m · n · 4ᴸ)time, L = word.length()
O(L)marked path and recursion
DFS + undoremove the cell on the way back

board 1–4 rows × 1–4 letters, rows of equal length · word 1–8 letters · case matters · capped at 120 tree nodes and 250 steps

board[r][c]vsword[i]

board blue = path · numbers = index in word · ring = cell being tried

word matched prefix · next letter in yellow

call tree one node per dfs call · edge = start cell or direction · dashed = returned false at once · off-board calls are not drawn

char[][] board;String word;boolean[][] path;public boolean exist(char[][] board, String word) { this.board = board; this.word = word; path = new boolean[board.length][board[0].length]; for (int r = 0; r < board.length; r++) { for (int c = 0; c < board[0].length; c++) { if (dfs(r, c, 0)) { return true; } } } return false;}private boolean dfs(int r, int c, int i) { if (i == word.length()) { return true; } if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || word.charAt(i) != board[r][c] || path[r][c]) { return false; } path[r][c] = true; boolean res = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1); path[r][c] = false; return res;}
(r, c)
—
i
—
path
{}
calls
0

Why it works

  1. Brute force lists every simple path of length L from every cell and compares its letters with the word. The number of such paths grows like 4ᴸ per start, and nothing stops a path early.
  2. Fail at the first wrong letter. A call returns false as soon as its cell is off the board, holds the wrong letter, or is already on the path. Only prefixes of the word are ever extended, so most branches die after one step.
  3. O(m · n · 4ᴸ) worst case. Each of the m·n starts can branch four ways per letter (three after the first, since the way back is on the path). The marked path and the recursion are at most L deep.
  4. Pitfall: forgetting path[r][c] = false. A cell used by a failed branch must become free again, or a later branch that needs it (like the "AAB" preset) reports false wrongly.
  5. Speed-ups: return false early if the board lacks enough of some letter, and search the reversed word when its last letter is rarer than its first. Word Search II (212) runs many words at once with a trie.