Word Search - Go Solution

LeetCode

— 2 min read

Solving the LeetCode "Word Search" Problem in Go

Difficulty: Medium | Tags: Array, String, Backtracking, Depth-First Search, Matrix

Introduction

The "Word Search" problem requires checking if a given word can be constructed from adjacent cells in a 2D grid, where adjacent cells are horizontally or vertically neighboring. This problem is a classic example of backtracking and depth-first search (DFS) applications.

Problem Analysis

Given an m x n grid of characters and a word, we need to determine if the word exists by moving to adjacent cells without reusing any cell. Examples demonstrate how words like "ABCCED" and "SEE" can be found, while "ABCB" cannot due to cell reuse constraints.

Solution Approach

The solution involves using DFS with backtracking. We iterate over each cell in the grid, and for each cell that matches the first character of the word, we initiate a DFS to explore all possible paths. During DFS, we mark visited cells to prevent reuse and backtrack if the current path does not lead to the solution.

Go Implementation


func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == word[0] {
                if dfs(board, word, i, j, 0, visited) {
                    return true
                }
            }
        }
    }
    return false
}
func dfs(board [][]byte, word string, i, j, index int, visited [][]bool) bool {
    if index == len(word) {
        return true
    }
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || visited[i][j] || board[i][j] != word[index] {
        return false
    }
    visited[i][j] = true
    if dfs(board, word, i+1, j, index+1, visited) ||
    dfs(board, word, i-1, j, index+1, visited) ||
    dfs(board, word, i, j+1, index+1, visited) ||
    dfs(board, word, i, j-1, index+1, visited) {
        return true
    }
    visited[i][j] = false
    return false
}

Complexity Analysis

Time Complexity: O(m * n * 4^L), where m and n are the grid dimensions, and L is the word length. The worst case involves exploring all 4 directions for each cell up to the word length.

Space Complexity: O(L) for the recursion stack, plus O(m * n) for the visited matrix, totaling O(m * n + L).

Testing and Examples

Test cases should include:

  • Example 1: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" → Output: true
  • Example 2: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" → Output: true
  • Example 3: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" → Output: false
  • Edge Case: Empty word → Output: true

Best Practices and Tips

Key takeaways include optimizing with early termination, using a visited matrix to track cell usage, and leveraging DFS for path exploration. Pruning unnecessary paths early can significantly improve performance for larger grids.

Read more