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

Introduction to Word Search II

Word Search II is a classic algorithmic problem frequently encountered in coding interviews and competitive programming. Given a 2D board of characters and a list of words, the task is to return all words from the list that can be found on the board. A 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 in a single word.

While the simpler Word Search I problem asks you to find a single word on the board, Word Search II scales this up to multiple words, which makes a naive approach extremely inefficient. The key insight is to use a Trie (prefix tree) data structure to efficiently search for all words simultaneously.

Why It Matters

This problem is a perfect test of several fundamental computer science concepts working together:

• Trie data structure: Efficient prefix-based string storage and lookup.
• Backtracking: Exploring all possible paths while pruning invalid branches.
• Graph traversal: Navigating a 2D grid using DFS.
• Time complexity optimization: Avoiding redundant work across multiple searches.

A naive solution that runs a separate DFS for each word would result in O(W * M * N * 4^L) time complexity, where W is the number of words, M and N are board dimensions, and L is the maximum word length. By using a Trie, we can reduce this significantly because we share the search across all words and prune branches early when no word in our dictionary shares the current prefix.

Understanding the Trie Data Structure

A Trie is a tree-like data structure where each node represents a character. Words are stored as paths from the root to leaf nodes (or to nodes marked as word endings). The beauty of a Trie for this problem is that when we explore the board, we can check at each step whether the current path forms a valid prefix of any word in our dictionary. If it doesn't, we immediately backtrack.

Trie Node Structure in Go

Let's start by defining our Trie node:

package main

import "fmt"

// TrieNode represents a node in the prefix tree
type TrieNode struct {
    children map[byte]*TrieNode
    word     string // non-empty if this node marks the end of a word
}

// NewTrieNode creates a new TrieNode
func NewTrieNode() *TrieNode {
    return &TrieNode{
        children: make(map[byte]*TrieNode),
        word:     "",
    }
}

Notice that instead of using a boolean flag to mark word endings, we store the actual word string. This is a convenient trick: when we reach a node during our DFS that has a non-empty word field, we know we've found a complete word, and we can add it directly to our results without reconstructing it from the path.

Building the Trie

Next, we insert all the words from our dictionary into the Trie:

// Insert adds a word into the trie
func (t *TrieNode) Insert(word string) {
    node := t
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if _, exists := node.children[ch]; !exists {
            node.children[ch] = NewTrieNode()
        }
        node = node.children[ch]
    }
    node.word = word
}

Each character of the word is traversed character by character, creating new nodes as needed. The final node stores the complete word string.

Implementing the DFS Backtracking Search

Now comes the core of the solution. We iterate over every cell in the board. For each cell, if its character exists as a child of the Trie root, we begin a DFS from that cell.

The FindWords Function

func findWords(board [][]byte, words []string) []string {
    // Build the trie from the word list
    root := NewTrieNode()
    for _, w := range words {
        root.Insert(w)
    }

    result := []string{}
    rows := len(board)
    cols := len(board[0])

    // Directions: up, down, left, right
    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    var dfs func(row, col int, node *TrieNode)
    dfs = func(row, col int, node *TrieNode) {
        ch := board[row][col]

        // Check if this character leads anywhere in the trie
        child, exists := node.children[ch]
        if !exists {
            return
        }

        // If we found a complete word, add it to results
        if child.word != "" {
            result = append(result, child.word)
            child.word = "" // Avoid duplicate entries for the same word
        }

        // Mark the cell as visited by temporarily changing its value
        board[row][col] = '#'

        // Explore all four directions
        for _, dir := range directions {
            newRow := row + dir[0]
            newCol := col + dir[1]
            if newRow >= 0 && newRow < rows &&
                newCol >= 0 && newCol < cols &&
                board[newRow][newCol] != '#' {
                dfs(newRow, newCol, child)
            }
        }

        // Restore the cell's original value (backtrack)
        board[row][col] = ch
    }

    // Start DFS from every cell
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            dfs(i, j, root)
        }
    }

    return result
}

How the Backtracking Works

The DFS function does several important things:

• Prefix check: It checks whether the current cell's character exists as a child in the current Trie node. If not, it returns immediately, pruning the search.
• Word collection: If the child node has a non-empty word field, the word is added to results. We then clear the word field to prevent duplicates if the same word can be formed through multiple paths.
• Visited marking: The current cell is temporarily marked with # to prevent revisiting it in the same path. This is an in-place technique that avoids allocating a separate visited matrix.
• Recursive exploration: The function recurses into all four adjacent cells that are within bounds and not yet visited.
• Backtracking: After exploring all directions, the original character is restored, allowing other paths to use this cell.

Complete Working Example

Let's put everything together with a main function and a test case:

package main

import "fmt"

// TrieNode represents a node in the prefix tree
type TrieNode struct {
    children map[byte]*TrieNode
    word     string
}

func NewTrieNode() *TrieNode {
    return &TrieNode{
        children: make(map[byte]*TrieNode),
        word:     "",
    }
}

func (t *TrieNode) Insert(word string) {
    node := t
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if _, exists := node.children[ch]; !exists {
            node.children[ch] = NewTrieNode()
        }
        node = node.children[ch]
    }
    node.word = word
}

func findWords(board [][]byte, words []string) []string {
    root := NewTrieNode()
    for _, w := range words {
        root.Insert(w)
    }

    result := []string{}
    rows := len(board)
    cols := len(board[0])
    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    var dfs func(row, col int, node *TrieNode)
    dfs = func(row, col int, node *TrieNode) {
        ch := board[row][col]
        child, exists := node.children[ch]
        if !exists {
            return
        }

        if child.word != "" {
            result = append(result, child.word)
            child.word = ""
        }

        board[row][col] = '#'
        for _, dir := range directions {
            newRow := row + dir[0]
            newCol := col + dir[1]
            if newRow >= 0 && newRow < rows &&
                newCol >= 0 && newCol < cols &&
                board[newRow][newCol] != '#' {
                dfs(newRow, newCol, child)
            }
        }
        board[row][col] = ch
    }

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            dfs(i, j, root)
        }
    }

    return result
}

func main() {
    board := [][]byte{
        {'o', 'a', 'a', 'n'},
        {'e', 't', 'a', 'e'},
        {'i', 'h', 'k', 'r'},
        {'i', 'f', 'l', 'v'},
    }
    words := []string{"oath", "pea", "eat", "rain"}

    found := findWords(board, words)
    fmt.Println("Found words:", found)
}

When you run this program, the output will be:

Found words: [oath eat]

The words "oath" and "eat" can be traced on the board through adjacent cells, while "pea" and "rain" cannot.

Complexity Analysis

Understanding the time and space complexity is crucial for evaluating this solution:

• Time Complexity: O(M * N * 4^L), where M is the number of rows, N is the number of columns, and L is the maximum length of any word in the dictionary. In the worst case, we explore all four directions from each cell up to depth L. However, the Trie pruning makes the practical performance much better because most paths are cut short when no matching prefix exists.
• Space Complexity: O(K * L), where K is the number of words and L is the average word length, for storing the Trie. The recursion stack uses O(L) space in the worst case.

Best Practices and Optimizations

1. Remove Leaf Nodes After Finding Words

One powerful optimization is to remove Trie nodes that no longer have any children after a word is found. This progressively shrinks the Trie during the search, making subsequent searches faster:

func (t *TrieNode) removeChild(ch byte) {
    delete(t.children, ch)
}

// In the DFS, after exploring all directions:
if len(child.children) == 0 {
    delete(node.children, ch)
}

This optimization is particularly effective when the board contains many of the dictionary words, as the Trie gets smaller with each discovery.

2. Use Arrays Instead of Maps for Children

If you know the character set is limited (for example, only lowercase English letters), using a fixed-size array of 26 elements instead of a map can improve performance due to better cache locality and the elimination of hash overhead:

type TrieNode struct {
    children [26]*TrieNode
    word     string
}

func (t *TrieNode) Insert(word string) {
    node := t
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if node.children[idx] == nil {
            node.children[idx] = NewTrieNode()
        }
        node = node.children[idx]
    }
    node.word = word
}

3. Early Termination

If the number of found words equals the total number of words in the dictionary, you can terminate the search early. This is a simple but effective optimization:

if len(result) == len(words) {
    return
}

4. Avoid String Concatenation in DFS

By storing the complete word at the terminal Trie node (as we did), we avoid building strings character by character during the DFS. This eliminates O(L) string operations at each step and is a significant performance win.

5. Handle Edge Cases

Always validate your inputs before processing:

func findWords(board [][]byte, words []string) []string {
    if len(board) == 0 || len(board[0]) == 0 || len(words) == 0 {
        return []string{}
    }
    // ... rest of the implementation
}

Common Pitfalls to Avoid

• Forgetting to backtrack: If you mark a cell as visited but forget to restore it, other paths will be blocked, leading to incorrect results.
• Duplicate words in results: The same word might be found through multiple paths. Clearing the word field after finding it prevents duplicates.
• Not pruning the Trie: Without prefix-based pruning, the solution degrades to checking every possible path, which is exponentially slow.
• Using a separate visited matrix: While this works, it adds memory overhead and allocation cost. The in-place marking technique is more efficient.

Conclusion

Solving Word Search II in Go elegantly combines the Trie data structure with DFS backtracking to efficiently search for multiple words on a 2D board simultaneously. The Trie enables shared prefix exploration and early pruning, transforming what would be an exponentially expensive naive search into a practical solution. By following the step-by-step approach outlined in this tutorial — building the Trie, implementing the DFS with in-place visited marking, and applying optimizations like node removal and array-based children — you can write a robust and performant solution. This problem serves as an excellent exercise in combining data structures, algorithms, and careful implementation details, and mastering it will strengthen your ability to tackle similar grid-based search problems in both interviews and real-world applications.