NUHMAN.com

Introduction

LeetCode 79: Word Search is a well-known grid-based problem that challenges your understanding of depth-first search (DFS) and backtracking. You're given a 2D board of characters and a word, and you must determine whether the word exists in the grid by moving horizontally or vertically to adjacent cells.

This is a classic problem for testing recursive search and grid traversal techniques.

Problem Statement

Given an m x n grid of characters board and a string word, return true if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

go

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

Output: true
go

word = "SEE"
Output: true

word = "ABCB"
Output: false

Approach: DFS + Backtracking

We iterate over every cell in the grid and:

1. Start DFS if the cell’s character matches the first letter of the word.
2. At each DFS call:

• If the current character matches the word's current index:
• Recursively search in 4 directions: up, down, left, right.
• Temporarily mark the cell as visited (e.g., using #).
• Restore the cell after backtracking.

This ensures each cell is used at most once in a path.

Go Implementation

go

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

    var dfs func(r, c, i int) bool
    dfs = func(r, c, i int) bool {
        if i == len(word) {
            return true
        }

        if r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word[i] {
            return false
        }

        temp := board[r][c]
        board[r][c] = '#' // mark as visited

        found := dfs(r+1, c, i+1) ||
                 dfs(r-1, c, i+1) ||
                 dfs(r, c+1, i+1) ||
                 dfs(r, c-1, i+1)

        board[r][c] = temp // backtrack
        return found
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if dfs(r, c, 0) {
                return true
            }
        }
    }
    return false
}

Explanation

• We check each cell to begin DFS from potential starting points.
• During DFS, we use temporary marking (#) to avoid revisiting.
• After the recursive calls, we restore the cell (backtracking).
• The search continues until we find the full word or exhaust the board.

Time and Space Complexity

MetricComplexityTime ComplexityO(m × n × 4^L)Space ComplexityO(L) (recursion depth)

Where:

• m and n are the dimensions of the board,
• L is the length of the word.

Each cell can branch up to 4 directions, and the search depth is up to L.

Edge Cases

• Empty board → return false.
• Word longer than total number of cells → return false.
• Duplicate characters → handled by marking visited.
• Multiple paths to match the word → any one path is sufficient.

Conclusion

LeetCode 79 tests your ability to traverse a 2D matrix using DFS and implement efficient backtracking. It's foundational for solving complex grid-based problems.

By solving this in Go, you’ll strengthen your understanding of recursion, matrix manipulation, and backtracking patterns—all essential in algorithmic problem-solving.