79. Word SearchMedium

Word Search

MediumArrayBacktracking·AmazonMicrosoft

Given a 2-D grid of characters board and a string word, return true if the word is present in the grid, otherwise return false.

For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Examples

Example 1

Inputword = "CAT"

Outputtrue

Example 2

Inputword = "BAT"

Outputfalse

1 ≤ board.length, board[i].length ≤ 5
1 ≤ word.length ≤ 10

Prerequisites

Before attempting this problem, you should be comfortable with:

Backtracking - Exploring all possible paths by making choices, recursing, and undoing choices
Depth-First Search (DFS) - Traversing a grid by exploring as far as possible along each branch before backtracking

1. Backtracking (Optimal)

Intuition

We want to check if the word can be formed by moving up/down/left/right in the grid, using each cell at most once in a single path.

Instead of keeping a separate visited matrix (extra space), we temporarily mark the current cell as used by replacing its character with a special value (like '#'). This means:

If we ever see '#', we know this cell is already in our current path → we can't reuse it.
After exploring from that cell, we restore the original character (this is the "backtrack" step), so other paths can use it.

Algorithm

Let ROWS, COLS be grid size. Define dfs(r, c, i) meaning: "Can we match word[i...] starting from cell (r, c)?" Base case: if i == len(word), we matched all characters → return true. Fail cases: if out of bounds, current cell doesn't match word[i], or cell is already used ('#') → return false. Mark the cell as used (set it to '#'). Try DFS in 4 directions with i + 1. Restore the cell back to its original character (backtrack). Run dfs(r, c, 0) from every cell (r, c). If any returns true, answer is true; otherwise false.

Time Complexity: O(M × 4^N) where M is the number of cells and N is the word length.

Space Complexity: O(N) for the recursion stack.

Visualizing Grid Search (DFS)

Notice how the algorithm searches neighbor by neighbor. A glowing trail follows the current matching path. If a branch fails, the trail shrinks backward, restoring the cells so they can be visited by other routes.

Word Match Tracker

Call Stack

—

READY—

Press ▶ or step forward to begin.

—

Target Word

Executing Code

class Solution:

    def exist(self, board: List[List[str]], word: str) -> bool:

        ROWS, COLS = len(board), len(board[0])

        def dfs(r, c, i):

            if i == len(word):

                return True

            if (r < 0 or c < 0 or r >= ROWS or c >= COLS or

                word[i] != board[r][c] or board[r][c] == '#'):

                return False

            board[r][c] = '#'

            res = (dfs(r + 1, c, i + 1) or

                   dfs(r - 1, c, i + 1) or

                   dfs(r, c + 1, i + 1) or

                   dfs(r, c - 1, i + 1))

            board[r][c] = word[i]

            return res

        for r in range(ROWS):

            for c in range(COLS):

                if dfs(r, c, 0):

                    return True

        return False

Common Pitfalls

Not Restoring the Cell After Backtracking

When marking a cell as visited by changing its value (e.g., to '#'), forgetting to restore the original character after exploring all neighbors will permanently modify the board. This causes other paths starting from different cells to incorrectly treat valid cells as already visited.

Checking Visited Before Matching Character

Placing the visited check before the character match check can cause subtle bugs depending on your implementation. If a cell is marked visited with a special character like '#', comparing board[r][c] != word[i] will correctly fail.

Discussion

…

Loading comments…

LeetMotion