LeetCode 79 - Word Search

In this problem, we are given a two dimensional grid of characters called board and a target string called word. The task is to determine whether the word can be formed by traversing the grid under a strict set of movement rules.

leetcodemediumarraystringbacktrackingdepth-first-searchmatrix

LeetCode Problem 79

Difficulty: 🟡 Medium
Topics: Array, String, Backtracking, Depth-First Search, Matrix

Solution

Problem Understanding

In this problem, we are given a two dimensional grid of characters called board and a target string called word. The task is to determine whether the word can be formed by traversing the grid under a strict set of movement rules.

A valid word construction must satisfy the following conditions:

  • You may start from any cell in the board.
  • Each next character in the word must come from a horizontally or vertically adjacent cell.
  • Diagonal movement is not allowed.
  • A single cell cannot be reused within the same word path.

The output is a boolean value:

  • Return true if the word can be formed.
  • Return false otherwise.

For example, suppose the board contains the letters:

A B C E
S F C S
A D E E

and the target word is "ABCCED".

A valid path exists:

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

where every move is horizontal or vertical, and no cell is reused.

The constraints are important because they guide the expected solution complexity:

  • 1 <= m, n <= 6
  • The board size is at most 6 x 6, meaning at most 36 cells.
  • 1 <= word.length <= 15

These limits are small enough that backtracking and depth first search are feasible. However, a naive exhaustive search can still become expensive because each character may branch into multiple possible directions.

Several edge cases are important to consider:

  • The board may contain many repeated letters, which creates many misleading search paths.
  • The word may be longer than the total number of cells in the board, which immediately makes the answer impossible.
  • The same character may appear multiple times, so the algorithm must correctly track visited cells.
  • A path may partially match the word and then fail later, so the algorithm must backtrack correctly.
  • The board may contain uppercase and lowercase letters, and comparisons are case sensitive.

Approaches

Brute Force Approach

The brute force idea is to try every possible path starting from every cell in the board.

For each starting position, we recursively explore all possible paths by moving up, down, left, or right. At each step, we check whether the current cell matches the corresponding character in the word.

If we successfully match all characters, the answer is true. If all possible paths fail, the answer is false.

This approach is correct because it exhaustively explores every valid path that could potentially form the word.

However, the brute force approach becomes expensive because each recursive call can branch into as many as four directions. The number of possible paths grows exponentially with the length of the word.

Without pruning, the complexity becomes extremely large.

Optimal Approach, Backtracking with DFS

The key insight is that this problem naturally forms a recursive search process.

At every character in the word, we only need to consider neighboring cells that:

  • Stay within bounds
  • Match the next required character
  • Have not already been used in the current path

This makes depth first search with backtracking the ideal technique.

Backtracking works well because:

  • We build one candidate path at a time.
  • If the path becomes invalid, we immediately abandon it.
  • We restore the board state after exploring each path so other searches can reuse the cells.

We can also add useful pruning:

  • If the current cell does not match the target character, stop immediately.
  • If the word length exceeds the total number of cells, return false immediately.

This dramatically reduces unnecessary exploration.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * 4^L) O(L) Tries all possible paths recursively
Optimal O(m * n * 4^L) O(L) DFS with pruning and backtracking

Here:

  • m is the number of rows
  • n is the number of columns
  • L is the length of the word

Although the asymptotic complexity appears the same, pruning makes the practical runtime much faster.

Algorithm Walkthrough

  1. First, compute the dimensions of the board.

We need the number of rows and columns for boundary checking during DFS traversal. 2. Check whether the word length exceeds the number of cells.

If len(word) > rows * cols, the word cannot possibly fit without reusing cells, so we return False. 3. Define a recursive DFS function.

The DFS function will track:

  • The current row
  • The current column
  • The current index in the word

This function answers the question:

"Can we complete the remaining portion of the word starting from this cell?" 4. Handle the success base case.

If the current index equals the word length, it means we matched every character successfully, so return True. 5. Validate the current cell.

Before continuing, verify:

  • The coordinates are within bounds
  • The cell matches the current target character
  • The cell has not already been visited

If any condition fails, return False. 6. Mark the current cell as visited.

We temporarily replace the character with a special marker such as "#".

This prevents revisiting the same cell within the current search path. 7. Explore all four directions.

Recursively search:

  • Up
  • Down
  • Left
  • Right

Each recursive call advances to the next character in the word. 8. Restore the original character.

After exploring all directions, restore the original board value.

This is the backtracking step. It ensures other paths can reuse this cell later. 9. Start DFS from every board cell.

Since the word may begin anywhere, iterate through the entire board and launch DFS from each position. 10. Return the final result.

If any DFS call succeeds, return True. Otherwise return False.

Why it works

The algorithm maintains an important invariant:

At every recursive call, the current path exactly matches the prefix word[0:index].

The DFS only continues when the current cell correctly matches the next required character. Backtracking guarantees that cells are reused only across different search paths, never within the same path.

Because the algorithm systematically explores all valid paths while rejecting invalid ones immediately, it correctly determines whether the word exists in the board.

Python Solution

from typing import List

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

        if len(word) > rows * cols:
            return False

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

            if (
                row < 0
                or row >= rows
                or col < 0
                or col >= cols
                or board[row][col] != word[index]
            ):
                return False

            temp = 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] = temp

            return found

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

        return False

The implementation begins by calculating the board dimensions. These values are reused throughout the DFS process for boundary checking.

The early pruning condition checks whether the word is longer than the total number of cells. Since cells cannot be reused, such a word is impossible to construct.

The recursive dfs function handles the core search logic. The parameter index represents the current character position in the word.

The base case:

if index == len(word):
    return True

means the entire word has been matched successfully.

The boundary and mismatch checks ensure that invalid paths terminate immediately. This pruning is essential for efficiency.

The board modification:

board[row][col] = "#"

marks the cell as visited. This avoids the need for a separate visited matrix and keeps the space complexity low.

The recursive exploration checks all four directions. If any direction succeeds, the result becomes True.

Finally, the original character is restored. This backtracking step ensures the board remains unchanged for future search paths.

Go Solution

func exist(board [][]byte, word string) bool {
    rows := len(board)
    cols := len(board[0])

    if len(word) > rows*cols {
        return false
    }

    var dfs func(int, int, int) bool

    dfs = func(row int, col int, index int) bool {
        if index == len(word) {
            return true
        }

        if row < 0 ||
            row >= rows ||
            col < 0 ||
            col >= cols ||
            board[row][col] != word[index] {
            return false
        }

        temp := board[row][col]
        board[row][col] = '#'

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

        board[row][col] = temp

        return found
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if dfs(row, col, 0) {
                return true
            }
        }
    }

    return false
}

The Go implementation follows the same logic as the Python solution.

A nested recursive function is created using a function variable declaration:

var dfs func(int, int, int) bool

This allows the function to recursively reference itself.

The board uses [][]byte instead of strings for individual characters, which makes in place modification straightforward.

The visited marking uses:

board[row][col] = '#'

just like the Python solution.

Go does not require special handling for integer overflow here because all indices remain extremely small under the problem constraints.

Worked Examples

Example 1

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

word = "ABCCED"

The algorithm starts scanning the board.

Step Position Character Needed Result
1 (0,0) A Match
2 (0,1) B Match
3 (0,2) C Match
4 (1,2) C Match
5 (2,2) E Match
6 (2,1) D Match

After matching all characters, DFS returns True.

Path taken:

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

Example 2

word = "SEE"

Search begins from multiple cells until it reaches:

Step Position Character Needed Result
1 (1,3) S Match
2 (2,3) E Match
3 (2,2) E Match

All characters are matched successfully.

Result:

True

Example 3

word = "ABCB"

Initial matching proceeds successfully:

Step Position Character Needed Result
1 (0,0) A Match
2 (0,1) B Match
3 (0,2) C Match

Now the algorithm needs another "B".

Possible neighbors:

Neighbor Value Valid
Left B Already visited
Right E No
Down C No
Up Out of bounds No

No valid continuation exists.

Backtracking eventually exhausts all possibilities.

Result:

False

Complexity Analysis

Measure Complexity Explanation
Time O(m * n * 4^L) Each cell may branch into four recursive directions
Space O(L) Recursive call stack depth equals word length

The DFS starts from every cell in the board, giving m * n starting points.

For each recursive step, the search may branch into as many as four directions. Since the recursion depth is at most L, the worst case becomes exponential.

The space complexity comes from the recursion stack. At most one recursive call exists for each character in the word.

Test Cases

from typing import List

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

        if len(word) > rows * cols:
            return False

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

            if (
                row < 0
                or row >= rows
                or col < 0
                or col >= cols
                or board[row][col] != word[index]
            ):
                return False

            temp = 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] = temp

            return found

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

        return False

solution = Solution()

# Example 1
assert solution.exist(
    [["A","B","C","E"],
     ["S","F","C","S"],
     ["A","D","E","E"]],
    "ABCCED"
) == True  # standard valid path

# Example 2
assert solution.exist(
    [["A","B","C","E"],
     ["S","F","C","S"],
     ["A","D","E","E"]],
    "SEE"
) == True  # another valid path

# Example 3
assert solution.exist(
    [["A","B","C","E"],
     ["S","F","C","S"],
     ["A","D","E","E"]],
    "ABCB"
) == False  # requires reusing a cell

# Single cell success
assert solution.exist([["A"]], "A") == True  # minimal valid case

# Single cell failure
assert solution.exist([["A"]], "B") == False  # minimal invalid case

# Word longer than total cells
assert solution.exist(
    [["A","B"],
     ["C","D"]],
    "ABCDE"
) == False  # impossible due to length

# Repeated letters with valid path
assert solution.exist(
    [["A","A","A"],
     ["A","A","A"],
     ["A","A","A"]],
    "AAAAAAAAA"
) == True  # uses every cell exactly once

# Repeated letters requiring reuse
assert solution.exist(
    [["A","A"],
     ["A","A"]],
    "AAAAA"
) == False  # not enough unique cells

# Complex backtracking path
assert solution.exist(
    [["C","A","A"],
     ["A","A","A"],
     ["B","C","D"]],
    "AAB"
) == True  # requires careful backtracking

# Case sensitivity check
assert solution.exist(
    [["a","B"],
     ["c","D"]],
    "AB"
) == False  # lowercase and uppercase differ
Test Why
"ABCCED" Standard successful traversal
"SEE" Valid path with different starting point
"ABCB" Prevents revisiting cells
Single cell success Smallest valid input
Single cell failure Smallest invalid input
Word longer than cells Early pruning condition
All repeated letters Stress test for backtracking
Repeated letters overflow Ensures no cell reuse
"AAB" case Validates complex backtracking
Case sensitivity Confirms exact character matching

Edge Cases

Word Longer Than Available Cells

A very important edge case occurs when the word length exceeds the total number of board cells.

For example:

board =
[
  ["A","B"],
  ["C","D"]
]

word = "ABCDE"

The board only contains four cells, but the word requires five characters. Since cells cannot be reused, the answer must immediately be False.

The implementation handles this efficiently with:

if len(word) > rows * cols:
    return False

This pruning avoids unnecessary DFS exploration.

Repeated Characters Causing Incorrect Reuse

Another common bug source is accidentally revisiting the same cell.

Consider:

board =
[
  ["A","B","C"]
]

word = "ABA"

A naive implementation might incorrectly reuse the first "A".

The solution prevents this by temporarily marking visited cells:

board[row][col] = "#"

This guarantees each cell is used at most once in the current path.

Heavy Backtracking Scenarios

Boards with many repeated letters can create huge numbers of misleading paths.

Example:

board =
[
  ["A","A","A"],
  ["A","A","A"],
  ["A","A","A"]
]

word = "AAAAAAAAB"

Most of the word matches successfully, but the final character fails.

Without proper backtracking, the algorithm could either miss valid paths or corrupt the board state.

The implementation restores every modified cell after recursion:

board[row][col] = temp

This ensures every DFS path starts with a clean and correct board state.