LeetCode 79 - Word Search

I came back to this problem after a long time and initially expected DFS to make it a quick solution. The search itself was straightforward, but the implementation and the possible optimizations gave me more to think about than the core algorithm did.

The problem asks whether a word can be formed from horizontally or vertically adjacent cells in a character board. I started DFS from every cell, temporarily marked each cell used by the current path, and restored it before returning.

---

Problem link and explanation

• Problem: 79. Word Search
• Summary: Given an m by n board and a word, return true if adjacent horizontal or vertical cells can form the word. A cell cannot be reused within the same path.

The first character may occur anywhere, so every board position is a possible DFS starting point. A branch continues only when the current cell matches the current word index, then moves up, down, left, or right from that position.

---

Approach

The DFS state consists of the current row, column, and word index. A branch fails when its position is outside the board or its character does not match.

if row < 0 or col < 0 or row >= len(board) or col >= len(board[0]):
    return False

if word_idx >= len(word) or board[row][col] != word[word_idx]:
    return False

Matching the final character completes the word. Otherwise, the current cell is replaced with # so the same path cannot enter it again.

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

The branch succeeds if any of the four neighboring searches finds the remaining suffix. I store that result, restore the character, and then return.

found = (
    self.dfs(board, word, row + 1, col, word_idx + 1) or
    self.dfs(board, word, row - 1, col, word_idx + 1) or
    self.dfs(board, word, row, col + 1, word_idx + 1) or
    self.dfs(board, word, row, col - 1, word_idx + 1)
)

board[row][col] = temp
return found

If the word contains more characters than the board contains cells, no path can form it. I found this early-return condition while reviewing the solution afterward and added row_len, column_len, and word_len so the comparison is explicit before DFS begins. It was a small optimization I had not considered in the first pass.

---

Troubleshooting

My first version used a two-dimensional visited array with the same dimensions as the board. I later replaced that structure with a temporary # marker in the board. A marked cell cannot match the next character, so the marker enforces the same no-reuse constraint without a separate array.

---

Complexity analysis

• Time complexity: O(m × n × 3^w)
  • DFS may start from every cell. After the first move, the previous cell cannot be reused, leaving at most three directions at each step. w is the word length. Working through this bound was also part of what made me examine the solution more closely.
• Space complexity: O(w)
  • The board stores the temporary visited state, while the recursion stack can grow to the word length.

---

Implementation code

from typing import List

class Solution:
    def dfs(
        self,
        board: List[List[str]],
        word: str,
        row: int,
        col: int,
        word_idx: int,
    ) -> bool:
        if row < 0 or col < 0 or row >= len(board) or col >= len(board[0]):
            return False

        if word_idx >= len(word) or board[row][col] != word[word_idx]:
            return False

        if word_idx == len(word) - 1:
            return True

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

        found = (
            self.dfs(board, word, row + 1, col, word_idx + 1)
            or self.dfs(board, word, row - 1, col, word_idx + 1)
            or self.dfs(board, word, row, col + 1, word_idx + 1)
            or self.dfs(board, word, row, col - 1, word_idx + 1)
        )

        board[row][col] = temp
        return found

    def exist(self, board: List[List[str]], word: str) -> bool:
        row_len = len(board)
        column_len = len(board[0])
        word_len = len(word)

        if row_len * column_len < word_len:
            return False

        for i in range(row_len):
            for j in range(column_len):
                if self.dfs(board, word, i, j, 0):
                    return True

        return False

---

Summary and reflection

This problem was more satisfying than I expected. It covered DFS, backtracking, two practical optimizations, and a time-complexity analysis that was worth working through instead of accepting at a glance. I have been trying to spend at least a little time examining those details before moving on, because simply passing the test cases would have missed most of what this solution had to teach.