Word Search

35 min · exist()

A word on this board may bend around corners, but it may never cross its own tracks.

Given a rectangular character grid board and a string word, return true when one path through the grid spells the word from first character to last. Consecutive characters must occupy 4-directionally adjacent cells—cells that share a top, bottom, left, or right edge.

A path may use each cell at most once. Diagonal moves don't count, and the path can't leave the board. In the judge's char[][] wire format, every cell is a one-character string.

Constraints

1 <= board.length <= 6
1 <= board[row].length <= 6, and every row has the same length
1 <= word.length <= 15
Board cells and word contain uppercase or lowercase English letters.

Hints

Try every starting cell

The first character may appear more than once. Start a search from each cell that matches word[0]; one successful path is enough.

Carry the next index

A search state needs a row, a column, and the index of the character being matched. From a match, try the four neighboring cells for the next index.

Mark, explore, restore

Temporarily replace the current cell with a marker that can't equal a letter. Search its neighbors, then restore the original character before returning. That blocks reuse without permanently changing the caller's board.

Follow-up

Before searching, how could character frequencies—or starting from the rarer end of the word—prune hopeless cases?

Visible cases

Examples

Example 1

ready

Input: board = [ [ "A", "B", "C", "E" ], [ "S", "F", "C", "S" ], [ "A", "D", "E", "E" ] ] word = "ABCCED"
Expected: true
Why: the path turns through adjacent cells without reusing one

Example 2

ready

Input: board = [ [ "A", "B", "C", "E" ], [ "S", "F", "C", "S" ], [ "A", "D", "E", "E" ] ] word = "SEE"
Expected: true
Why: a valid path starts at the S in the final column

Example 3

ready

Input: board = [ [ "A", "B", "C", "E" ], [ "S", "F", "C", "S" ], [ "A", "D", "E", "E" ] ] word = "ABCB"
Expected: false
Why: finishing the word would require using the same B twice

Interview signal

Asked at

AmazonMetaMicrosoftBloomberg

Depth-first search + visited set

Depth-first search (DFS) follows one path as far as it can before returning to try another. Start DFS from every cell. A set of (row, column) positions records which cells the current path has already used.

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    visited: set[tuple[int, int]] = set()
 
    def search(row: int, col: int, index: int) -> bool:
        if not (0 <= row < rows and 0 <= col < cols):
            return False
        if (row, col) in visited or board[row][col] != word[index]:
            return False
        if index == len(word) - 1:
            return True
 
        visited.add((row, col))
        found = (
            search(row + 1, col, index + 1)
            or search(row - 1, col, index + 1)
            or search(row, col + 1, index + 1)
            or search(row, col - 1, index + 1)
        )
        visited.remove((row, col))
        return found
 
    return any(
        search(row, col, 0)
        for row in range(rows)
        for col in range(cols)
    )

From each starting cell, a path can branch in at most four directions for up to L characters. Time O(m · n · 4ᴸ), space O(L) for the visited set and call stack.

In-place backtracking

This is the backtracking pattern: choose a cell, mark it as used, explore, then undo the mark. The board itself can hold the visited state. # is safe because the input contains letters only.

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    if len(word) > rows * cols:
        return False
 
    def search(row: int, col: int, index: int) -> bool:
        if not (0 <= row < rows and 0 <= col < cols):
            return False
        if board[row][col] != word[index]:
            return False
        if index == len(word) - 1:
            return True
 
        saved = board[row][col]
        board[row][col] = "#"
        found = (
            search(row + 1, col, index + 1)
            or search(row - 1, col, index + 1)
            or search(row, col + 1, index + 1)
            or search(row, col - 1, index + 1)
        )
        board[row][col] = saved
        return found
 
    for row in range(rows):
        for col in range(cols):
            if search(row, col, 0):
                return True
    return False

Restoration happens before every recursive call returns, including a successful one, so the caller receives its original board. Time O(m · n · 4ᴸ), space O(L) for the call stack; the separate visited set is gone.

The marker is more than a memory trick. It makes "this cell belongs to the current path" part of the same choose–explore–undo rhythm used throughout the backtracking pattern.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayboard: char[][] · word: string

Expected

true

Run: visible + custom · Submit: full suite