NUHMAN.com

🧩 Problem Statement

Given an m x n board of characters and a list of strings words, return all words on the board.

You may search words in any direction, but each cell may only be used once per word.

📘 Example

go

Input:
board = [["o","a","a","n"],
         ["e","t","a","e"],
         ["i","h","k","r"],
         ["i","f","l","v"]]
words = ["oath","pea","eat","rain"]

Output:
["eat","oath"]

🧠 Approach

1. Trie Construction: Store the list of words in a Trie for efficient prefix matching.
2. DFS + Backtracking: From each cell, explore neighbors recursively:

• Prune paths early if current prefix doesn't exist in Trie.
• Mark visited cells temporarily (e.g., set to #).
• Restore cells after recursion.

✅ Go Implementation

go

package main

import "fmt"

type TrieNode struct {
    children map[byte]*TrieNode
    word     string
}

func findWords(board [][]byte, words []string) []string {
    root := buildTrie(words)
    result := []string{}

    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            dfs(board, i, j, root, &result)
        }
    }
    return result
}

func buildTrie(words []string) *TrieNode {
    root := &TrieNode{children: make(map[byte]*TrieNode)}
    for _, word := range words {
        node := root
        for i := 0; i < len(word); i++ {
            ch := word[i]
            if node.children[ch] == nil {
                node.children[ch] = &TrieNode{children: make(map[byte]*TrieNode)}
            }
            node = node.children[ch]
        }
        node.word = word // mark end of word
    }
    return root
}

func dfs(board [][]byte, i, j int, node *TrieNode, result *[]string) {
    ch := board[i][j]
    if ch == '#' || node.children[ch] == nil {
        return
    }

    node = node.children[ch]
    if node.word != "" {
        *result = append(*result, node.word)
        node.word = "" // avoid duplicates
    }

    board[i][j] = '#' // mark visited

    dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // right, down, left, up
    for _, d := range dirs {
        ni, nj := i+d[0], j+d[1]
        if ni >= 0 && nj >= 0 && ni < len(board) && nj < len(board[0]) {
            dfs(board, ni, nj, node, result)
        }
    }

    board[i][j] = ch // backtrack
}

📦 Example Usage

go

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"}

    fmt.Println(findWords(board, words)) // Output: ["oath", "eat"]
}

⏱️ Time & Space Complexity

• Time Complexity:
• Trie construction: O(W * L) where W = number of words, L = average word length.
• DFS: O(M * N * 4^L), where MxN is board size and L is max word length.
• Space Complexity:
• Trie: O(W * L)
• DFS call stack: O(L)

🧠 Key Concepts

• Trie for efficient prefix checks
• DFS with backtracking
• Avoid duplicates by setting node.word = "" after match