Word Search

The problem

You are given board, a grid of single letters, and a string word. Return true if there is a path of cells whose letters, read in order, spell word, and false if there is none. The path may start at any cell. Each step moves to the cell directly above, below, left or right of the current one, never diagonally. A cell may be used only once in a path, so the path cannot step back onto a cell it has already used.

What to write

function solve(board: string[][], word: string): boolean

Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"

Output
true

Input
board = [["A","B"],["C","D"]]
word = "ABCB"

Output
false

Constraints

Board dimensions are at most 6 × 6; word is nonempty.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The board is small, at most 6 by 6, so trying a lot of paths is affordable. But a path may not use a cell twice, so at every step you need to know which cells the current path already stands on.

2. Hint 2: Ask a smaller question

   Put a finger on a cell that holds the first letter of word. Which cells can the finger move to for the second letter? If you follow one of them and get stuck a few letters later, where do you go back to, and what do you try there?

3. Hint 3: Name the pattern

   A path is a series of choices: which neighbor comes next? A wrong choice only shows up some letters later. That signals backtracking: take a step, search on from there, and when that fails, undo the step and try the next neighbor. Mark each cell the current path uses, and remove the mark when you step back off that cell. Read the lesson on backtracking.

4. Hint 4: State the invariant

   While the search stands on a cell, the marked cells are exactly the cells of the current path, and their letters spell the beginning of word in order. When a call returns, its own cell has its letter back, so the board is again as that call found it.

5. Hint 5: Sketch the pseudocode

   search(cell, i): if i is the length of word, return true. Off the board, or not holding letter i: return false. Swap the letter for a mark. Run search on the four neighbors with i + 1 until one returns true. Put the letter back and return the result. Start search(cell, 0) from every cell until one returns true.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Try each starting cell and backtrack through matching neighbors, marking and restoring visited cells on each path.

The slow way

List every path of cells that is as long as the word, from every starting cell, and only then compare its letters with the word. It is correct, but most of the walking is wasted: the board of example 1 has 344 paths of six cells, and a path whose first letter is already wrong is still walked to its end.

The insight

A path that is wrong at its second letter cannot be saved by anything that comes after. So check each letter at the moment you step on its cell, and give up that direction at once when it does not match. Only paths that still spell the beginning of the word are ever continued.

Step by step

1. All letters of word are matched: the word is on the board. No letter is left to match, so every letter of the word already has its cell. This test comes first, because the cell handed to this call may be off the board.
2. A cell off the board or with the wrong letter ends this path. A path can only continue through a real cell that holds the letter needed now. A cell that this path already uses holds the mark instead of a letter, so it fails the same test.
3. Mark the cell as used so this path cannot step on it again. The rules allow each cell once per path. Writing a mark over the letter makes any later visit by this path fail the letter test, so no separate list of used cells is needed.
4. Look for the next letter in the four neighboring cells. The next letter must be in a cell that shares a side with this one: below, above, right or left. As soon as one direction finds the rest of the word, the other directions are not tried.
5. Put the letter back and report whether the rest was found. The mark belongs to this path only. Once this cell's neighbors have been tried, a different path may need the cell, so its letter returns. The caller needs the result to decide whether to keep looking.
6. Try every cell as the place where the word starts. The word may begin anywhere on the board, so each cell gets a search that asks for the first letter. The first search that succeeds settles the answer, and the rest are skipped.
7. No starting cell worked: the word is not on the board. Every start was tried, and from each one every path that matched letter by letter was followed until it failed. So no path spells the word.

The same numbered steps are the comments in each solution.

function solve(board, word) {
  function visit(r, c, i) {
    // 1. All letters of word are matched: the word is on the board
    if (i === word.length) return true;
    // 2. A cell off the board or with the wrong letter ends this path
    // Reading off the board gives undefined, which is never equal to a letter.
    if (board[r]?.[c] !== word[i]) return false;
    // 3. Mark the cell as used so this path cannot step on it again
    const ch = board[r][c];
    board[r][c] = "#";
    // 4. Look for the next letter in the four neighboring cells
    const found =
      visit(r + 1, c, i + 1) ||
      visit(r - 1, c, i + 1) ||
      visit(r, c + 1, i + 1) ||
      visit(r, c - 1, i + 1);
    // 5. Put the letter back and report whether the rest was found
    board[r][c] = ch;
    return found;
  }
  // 6. Try every cell as the place where the word starts
  for (let r = 0; r < board.length; r++)
    for (let c = 0; c < board[0].length; c++)
      if (visit(r, c, 0)) return true;
  // 7. No starting cell worked: the word is not on the board
  return false;
}

function solve(board: string[][], word: string): boolean {
  function visit(r: number, c: number, i: number): boolean {
    // 1. All letters of word are matched: the word is on the board
    if (i === word.length) return true;
    // 2. A cell off the board or with the wrong letter ends this path
    // Reading off the board gives undefined, which is never equal to a letter.
    if (board[r]?.[c] !== word[i]) return false;
    // 3. Mark the cell as used so this path cannot step on it again
    const ch = board[r][c];
    board[r][c] = "#";
    // 4. Look for the next letter in the four neighboring cells
    const found =
      visit(r + 1, c, i + 1) ||
      visit(r - 1, c, i + 1) ||
      visit(r, c + 1, i + 1) ||
      visit(r, c - 1, i + 1);
    // 5. Put the letter back and report whether the rest was found
    board[r][c] = ch;
    return found;
  }
  // 6. Try every cell as the place where the word starts
  for (let r = 0; r < board.length; r++)
    for (let c = 0; c < board[0].length; c++) if (visit(r, c, 0)) return true;
  // 7. No starting cell worked: the word is not on the board
  return false;
}

def solve(board, word):
    # The size of the board, for the off-the-board test below.
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, i):
        # 1. All letters of word are matched: the word is on the board
        if i == len(word):
            return True
        # 2. A cell off the board or with the wrong letter ends this path
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
            return False
        # 3. Mark the cell as used so this path cannot step on it again
        letter = board[r][c]
        board[r][c] = "#"
        # 4. Look for the next letter in the four neighboring cells
        found = (
            backtrack(r + 1, c, i + 1)
            or backtrack(r - 1, c, i + 1)
            or backtrack(r, c + 1, i + 1)
            or backtrack(r, c - 1, i + 1)
        )
        # 5. Put the letter back and report whether the rest was found
        board[r][c] = letter
        return found

    # 6. Try every cell as the place where the word starts
    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    # 7. No starting cell worked: the word is not on the board
    return False

Example 2, traced

Input
board = [["A","B"],["C","D"]]
word = "ABCB"

Output
false

Why it works

A path that spells the word starts at some cell and moves to a neighbor for each next letter. The search tries every start and every neighbor of each matched cell, and only the current path's cells are marked, because failed attempts put their letters back. So that path is never blocked. A wrong path is never accepted: every letter is checked against its cell.

Time and space

Time O(rows · cols · 4^L), extra space O(L). Every cell is a start: rows × cols of them. Each matched letter branches to 4 neighbors, up to L letters deep, L being the word's length: about 4^L calls per start, so O(rows · cols · 4^L) time. Calls nest at most L + 1 deep: O(L) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Put the letter back once a cell's neighbors have been tried. Otherwise a failed attempt leaves its cells marked for good: on the row B, A, A the word AAB, which reads from right to left, is reported missing.
• Mark a cell before you search its neighbors. Without the mark, a path can step back onto a cell it already used: on the row A, B the word ABA is reported found, although there is only one A.
• A failed start must not end the search. Return early only on success, and answer false after the last cell. Returning the first start's result either way misses the word A on the row B, A.

Pattern

Backtracking. Builds on Permutations.

Keep going