Find a Word in a Letter Grid | Practice

You are given board, a grid of letters (each cell holds one uppercase letter), and a string word. Return true if you can spell word by starting at any cell and stepping to a neighbouring cell for each next letter, and false otherwise.

Neighbours share a side: up, down, left or right, never diagonally. A path may not use the same cell twice.

Example 1

Input: board = [["C", "A", "T", "S"], ["O", "R", "E", "D"], ["D", "O", "G", "E"]], word = "CARE"
Output: true

Start at the top-left C, step right to A, down to R, then right to E.

Example 2

Input: board = [["C", "A", "T", "S"], ["O", "R", "E", "D"], ["D", "O", "G", "E"]], word = "CODE"
Output: false

C, O and D run down the first column, but no E touches that D, and the other D has no O next to it.

Example 3

Input: board = [["C", "A", "T", "S"], ["O", "R", "E", "D"], ["D", "O", "G", "E"]], word = "ERE"
Output: false

The only E next to the R is the one you would start from, and a cell can't be used twice.

Constraints

The board has 1 to 6 rows and 1 to 6 columns.
word has 1 to 15 letters.
The board and word hold only uppercase English letters.

Show the pattern

Backtracking

A match is a path through neighbouring cells that never reuses a cell. You step in, go deeper while the letters keep matching, and step back out to try another direction when they don't: backtracking on a grid.

See backtracking in a visualiser

Show the approach

Try every cell as a starting point with a recursive helper found(r, c, i), which asks whether word[i:] can be traced starting at cell (r, c):

If (r, c) is off the board, already on the current path, or doesn't hold word[i], it can't.
If i is the last index, the whole word is traced.
Otherwise put (r, c) on the path, try the four neighbours with i + 1, then take (r, c) off the path again (the backtracking step) and report whether any neighbour succeeded.

A set of cells on the path does the marking; writing a placeholder into the board and restoring it afterwards works too. The search stops at the first full match. The recursion is only as deep as the word is long.

Time: O(rows · cols · 3^L) for a word of length L: after the first step, each step has at most three new directions · Space: O(L) for the path and the recursion

Brush up firstDepth-First Search visualiser