LeetCode 79: Word Search

Problem Restatement

We are given an m x n grid of characters called board and a string called word.

We need to return True if word can be formed by walking through the grid.

The walk must follow these rules:

The official statement asks whether word exists in the grid, where adjacent cells are horizontally or vertically neighboring, and the same cell may not be used more than once. The common examples include board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], where "ABCCED" returns true.

Input and Output

Function shape:

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        ...

Examples

Example 1:

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

One valid path is:

A -> B -> C -> C -> E -> D

So the answer is:

True

Example 2:

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

One valid path is:

S -> E -> E

So the answer is:

True

Example 3:

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

The path would need to reuse the first B.

That is not allowed.

So the answer is:

False

First Thought: Try Every Starting Cell

The word can begin at any cell whose character matches word[0].

So a natural first idea is:

1. Try every cell as a starting point.
2. From that cell, search for the next character.
3. Continue until the whole word is matched.

This is a graph search problem on a grid.

Each cell has up to four neighbors:

up, down, left, right

Since we may need to undo choices when a path fails, the search needs backtracking.

Key Insight

At each step, we are trying to match:

word[index]

at position:

board[row][col]

A recursive search can answer this question:

“Can we match word[index:] starting from cell (row, col)?”

If the current cell does not match word[index], this path fails.

If it matches, we temporarily mark the cell as used, then try the four neighbors for word[index + 1].

After trying those neighbors, we restore the cell so it can be used in a different path.

That restore step is the backtracking step.

Algorithm

Let:

rows = len(board)
cols = len(board[0])

Define a DFS function:

dfs(row, col, index)

It returns whether we can match word[index:] starting from (row, col).

Inside dfs:

1. If index == len(word), all characters are matched.
2. If (row, col) is outside the board, return False.
3. If board[row][col] != word[index], return False.
4. Temporarily mark board[row][col] as visited.
5. Recursively search the four neighboring cells for index + 1.
6. Restore the original character.
7. Return whether any neighbor worked.

The outer function tries every cell as a starting position.

If any starting position works, return True.

Otherwise, return False.

Walkthrough

Use this board:

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

Start at cell (0, 0):

board[0][0] = "A"
word[0] = "A"

This matches.

Now we need word[1], which is "B".

From (0, 0), the valid neighboring cells are:

(1, 0) = "S"
(0, 1) = "B"

The cell (0, 1) matches "B".

Now we need "C".

From (0, 1), move to (0, 2):

board[0][2] = "C"

Now we need another "C".

From (0, 2), move to (1, 2):

board[1][2] = "C"

Now we need "E".

From (1, 2), move to (2, 2):

board[2][2] = "E"

Now we need "D".

From (2, 2), move to (2, 1):

board[2][1] = "D"

All characters are matched, so the answer is True.

Correctness

The DFS only accepts a cell when its character equals the current character in word.

Therefore, every path accepted by the algorithm spells the word in the correct order.

The DFS only moves to one of four neighbors:

(row + 1, col)
(row - 1, col)
(row, col + 1)
(row, col - 1)

Therefore, every accepted path uses only horizontally or vertically adjacent cells.

Before exploring neighbors, the algorithm marks the current cell as visited. While that recursive path is active, the same cell cannot be used again. Therefore, every accepted path uses each cell at most once.

Now consider any valid path that exists in the board. The outer loop tries the first cell of that path as a starting cell. From there, the DFS tries all four legal directions at each step. Since the valid path uses only legal moves and matching characters, the DFS can follow that exact path and eventually match every character.

So if a valid path exists, the algorithm returns True. If the algorithm returns True, it has found a path satisfying all rules. Therefore, the algorithm is correct.

Complexity

Let:

R = number of rows
C = number of columns
L = len(word)

From each cell, DFS may branch into up to four directions for the first move. After that, it usually has at most three useful directions because it cannot immediately go back to the previous cell.

A tight common bound is:

O(R * C * 4 * 3^(L - 1))

A simpler upper bound is:

O(R * C * 4^L)

The implementation below marks cells in place, so it does not need a separate visited set.

Implementation

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows = len(board)
        cols = len(board[0])

        def dfs(row: int, col: int, index: int) -> bool:
            if index == len(word):
                return True

            if row < 0 or row >= rows:
                return False

            if col < 0 or col >= cols:
                return False

            if board[row][col] != word[index]:
                return False

            original = board[row][col]
            board[row][col] = "#"

            found = (
                dfs(row + 1, col, index + 1)
                or dfs(row - 1, col, index + 1)
                or dfs(row, col + 1, index + 1)
                or dfs(row, col - 1, index + 1)
            )

            board[row][col] = original
            return found

        for row in range(rows):
            for col in range(cols):
                if dfs(row, col, 0):
                    return True

        return False

Code Explanation

We first store the board size:

rows = len(board)
cols = len(board[0])

The helper function receives a cell and the current index in word:

def dfs(row: int, col: int, index: int) -> bool:

If index == len(word), then every character has been matched:

if index == len(word):
    return True

Then we reject invalid cells:

if row < 0 or row >= rows:
    return False

if col < 0 or col >= cols:
    return False

Then we reject mismatched characters:

if board[row][col] != word[index]:
    return False

If the cell matches, we save its original character:

original = board[row][col]

Then we mark it as visited:

board[row][col] = "#"

This works because the board contains English letters, so "#" cannot be confused with a valid board character.

Then we try all four legal directions:

found = (
    dfs(row + 1, col, index + 1)
    or dfs(row - 1, col, index + 1)
    or dfs(row, col + 1, index + 1)
    or dfs(row, col - 1, index + 1)
)

If any direction works, found becomes True.

Before returning, we restore the cell:

board[row][col] = original

This is necessary because the same cell may be used in a different starting path or a different branch.

The outer loop tries all starting cells:

for row in range(rows):
    for col in range(cols):
        if dfs(row, col, 0):
            return True

If none works, the word does not exist:

return False

Testing

def run_tests():
    s = Solution()

    board1 = [
        ["A", "B", "C", "E"],
        ["S", "F", "C", "S"],
        ["A", "D", "E", "E"],
    ]

    assert s.exist([row[:] for row in board1], "ABCCED") is True
    assert s.exist([row[:] for row in board1], "SEE") is True
    assert s.exist([row[:] for row in board1], "ABCB") is False

    board2 = [["A"]]
    assert s.exist([row[:] for row in board2], "A") is True
    assert s.exist([row[:] for row in board2], "B") is False

    board3 = [
        ["C", "A", "A"],
        ["A", "A", "A"],
        ["B", "C", "D"],
    ]
    assert s.exist([row[:] for row in board3], "AAB") is True

    board4 = [
        ["A", "B"],
        ["C", "D"],
    ]
    assert s.exist([row[:] for row in board4], "AD") is False

    print("all tests passed")

run_tests()

Test meaning: