Solving Word Search in Go: Step-by-Step Guide

Introduction to the Word Search Problem

The Word Search problem is a classic algorithmic challenge that appears frequently in coding interviews and competitive programming. Given a 2D grid of characters and a target word, your task is to determine whether the word can be constructed from letters of sequentially adjacent cells. Adjacent cells are those horizontally or vertically neighboring, and the same cell cannot be used more than once in a single construction.

This problem is essentially a graph traversal challenge disguised as a grid problem. It tests your understanding of depth-first search (DFS), backtracking, and state management. In this tutorial, we will walk through solving the Word Search problem in Go, from a naive approach to an optimized solution.

Why the Word Search Problem Matters

Beyond being a popular interview question at companies like Amazon, Google, and Microsoft, the Word Search problem has real-world applications. It models scenarios such as:

• Pathfinding in grids: Robot navigation where each move corresponds to a letter match.
• Pattern recognition: Detecting sequences in 2D data like images or sensor matrices.
• Game development: Implementing word puzzle games similar to Boggle.
• Bioinformatics: Searching for nucleotide sequences in genomic data matrices.

Mastering this problem sharpens your ability to combine recursion, backtracking, and pruning techniques — skills that transfer directly to more complex problems like N-Queens, Sudoku solvers, and combinatorial search.

Understanding the Problem Statement

Let us formalize the problem. You are given:

• An m x n board of characters.
• A string word.

You must return true if the word exists in the grid. The word can be constructed from letters of adjacent cells (up, down, left, right), and each cell may only be used once per search path.

For example, given the board:

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

and the word "ABCCED", the answer is true. For the word "SEE", the answer is also true. For the word "ABCB", the answer is false because the same cell cannot be reused.

Choosing the Right Algorithm

The natural approach is to perform a DFS from every cell whose character matches the first letter of the word. At each step, we check whether the current cell matches the corresponding character in the word, mark it as visited, and recursively explore its four neighbors. If any path successfully matches the entire word, we return true. If no path works, we backtrack by unmarking the cell and trying a different direction.

This is a textbook backtracking algorithm. The time complexity is O(m * n * 4^L), where L is the length of the word, because from each starting cell we may explore up to four directions at each of the L levels of recursion. The space complexity is O(L) for the recursion stack.

Step-by-Step Implementation in Go

Step 1: Defining the Function Signature

We start by defining the main function that accepts the board and the word:

package main

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

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if dfs(board, word, i, j, 0) {
                return true
            }
        }
    }
    return false
}

The outer loops iterate over every cell in the board, attempting to start a DFS from each cell that might match the first character. The actual matching logic is delegated to the dfs helper function.

Step 2: Implementing the DFS Helper

The DFS function is the heart of the solution. It checks whether the current cell matches the expected character, marks the cell as visited, explores neighbors, and backtracks if necessary.

func dfs(board [][]byte, word string, i, j, index int) bool {
    // Base case: all characters matched
    if index == len(word) {
        return true
    }

    // Boundary and character checks
    if i < 0 || i >= len(board) ||
        j < 0 || j >= len(board[0]) ||
        board[i][j] != word[index] {
        return false
    }

    // Mark the cell as visited by temporarily changing its value
    temp := board[i][j]
    board[i][j] = '#'

    // Explore all four directions
    found := dfs(board, word, i+1, j, index+1) ||
        dfs(board, word, i-1, j, index+1) ||
        dfs(board, word, i, j+1, index+1) ||
        dfs(board, word, i, j-1, index+1)

    // Backtrack: restore the original character
    board[i][j] = temp

    return found
}

Notice how we mark a cell as visited by replacing its character with a sentinel value '#'. This avoids allocating a separate visited matrix, saving memory. After exploring all directions, we restore the original character so other search paths can use the cell.

Step 3: Putting It All Together

Here is the complete, runnable program with a main function that demonstrates the solution:

package main

import "fmt"

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

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if dfs(board, word, i, j, 0) {
                return true
            }
        }
    }
    return false
}

func dfs(board [][]byte, word string, i, j, index int) bool {
    if index == len(word) {
        return true
    }

    if i < 0 || i >= len(board) ||
        j < 0 || j >= len(board[0]) ||
        board[i][j] != word[index] {
        return false
    }

    temp := board[i][j]
    board[i][j] = '#'

    found := dfs(board, word, i+1, j, index+1) ||
        dfs(board, word, i-1, j, index+1) ||
        dfs(board, word, i, j+1, index+1) ||
        dfs(board, word, i, j-1, index+1)

    board[i][j] = temp

    return found
}

func main() {
    board := [][]byte{
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'},
    }

    words := []string{"ABCCED", "SEE", "ABCB"}
    for _, w := range words {
        fmt.Printf("Word %q exists: %v\n", w, exist(board, w))
    }
}

Running this program produces the following output:

Word "ABCCED" exists: true
Word "SEE" exists: true
Word "ABCB" exists: false

Optimizing the Solution

Early Pruning with Frequency Counts

One powerful optimization is to check whether the board even contains enough of each character to form the word. If the word requires more occurrences of a character than the board has, we can immediately return false without running any DFS.

func existOptimized(board [][]byte, word string) bool {
    if len(board) == 0 || len(board[0]) == 0 {
        return len(word) == 0
    }

    // Count characters on the board
    count := make(map[byte]int)
    for i := range board {
        for j := range board[i] {
            count[board[i][j]]++
        }
    }

    // Check if the board has enough of each character
    for i := 0; i < len(word); i++ {
        count[word[i]]--
        if count[word[i]] < 0 {
            return false
        }
    }

    // Optional: reverse the word if the last character is rarer
    // This reduces the branching factor at the start of the search
    if count[word[0]] > count[word[len(word)-1]] {
        word = reverseString(word)
    }

    rows := len(board)
    cols := len(board[0])
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if dfs(board, word, i, j, 0) {
                return true
            }
        }
    }
    return false
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

The word-reversal trick is subtle but effective. By starting the search from the rarer end of the word, we reduce the number of starting positions and prune invalid paths earlier, often dramatically improving performance on large boards.

Using a Visited Matrix Instead of Mutation

While mutating the board in place is memory efficient, it can be risky if the board must remain unchanged after the function returns. In such cases, use a separate visited matrix:

func existWithVisited(board [][]byte, word string) bool {
    rows := len(board)
    cols := len(board[0])
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    var backtrack func(i, j, index int) bool
    backtrack = func(i, j, index int) bool {
        if index == len(word) {
            return true
        }
        if i < 0 || i >= rows || j < 0 || j >= cols ||
            visited[i][j] || board[i][j] != word[index] {
            return false
        }

        visited[i][j] = true
        found := backtrack(i+1, j, index+1) ||
            backtrack(i-1, j, index+1) ||
            backtrack(i, j+1, index+1) ||
            backtrack(i, j-1, index+1)
        visited[i][j] = false

        return found
    }

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if backtrack(i, j, 0) {
                return true
            }
        }
    }
    return false
}

This version uses an O(m * n) visited matrix but leaves the original board untouched, which is safer for production code where the input may be shared or reused.

Best Practices

• Always validate inputs: Handle empty boards and empty words explicitly to avoid index-out-of-bounds panics.
• Prefer in-place marking when safe: Mutating the board saves memory and avoids allocation overhead, but only use it when the caller does not need the original board afterward.
• Prune aggressively: Character frequency checks and word reversal can cut runtime significantly on adversarial inputs.
• Keep recursion shallow: For very long words, consider converting the recursive DFS to an iterative stack-based approach to avoid stack overflow.
• Test edge cases: Include tests for single-cell boards, words longer than the total number of cells, and boards with repeated characters.
• Write table-driven tests: Go's testing package makes table-driven tests easy and readable, which is ideal for a problem with many input variations.

Writing Tests for the Solution

A robust test suite ensures your solution handles edge cases correctly. Here is an example using Go's table-driven test pattern:

package main

import "testing"

func TestExist(t *testing.T) {
    board := [][]byte{
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'},
    }

    tests := []struct {
        name     string
        word     string
        expected bool
    }{
        {"exists forward", "ABCCED", true},
        {"exists simple", "SEE", true},
        {"reuses cell", "ABCB", false},
        {"single char exists", "A", true},
        {"single char missing", "Z", false},
        {"empty word", "", true},
        {"word too long", "ABCDEFGHIJ", false},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            // Copy board to avoid mutation across tests
            b := make([][]byte, len(board))
            for i := range board {
                b[i] = append([]byte(nil), board[i]...)
            }
            result := exist(b, tt.word)
            if result != tt.expected {
                t.Errorf("exist(%q) = %v, want %v", tt.word, result, tt.expected)
            }
        })
    }
}

Note that we copy the board before each test case because the in-place mutation strategy would otherwise corrupt the board for subsequent tests. This is a subtle but important detail when testing backtracking solutions.

Conclusion

The Word Search problem is an excellent exercise in combining depth-first search with backtracking. By starting from a straightforward recursive solution and layering on optimizations like character frequency pruning and word reversal, you can build a solution that is both correct and efficient. Go's simplicity and strong support for recursion make it a great language for implementing this kind of algorithm. Whether you are preparing for interviews or building a word puzzle game, the techniques covered here — in-place state marking, careful boundary checking, and aggressive pruning — will serve you well across a wide range of combinatorial search problems.