Word Search in Grid Using Backtracking in DSA Go

Mental Model

We try to find the word by exploring each letter in the grid and moving step-by-step in all directions, going back if a path doesn't work.

Analogy: Imagine searching for a hidden path in a maze by trying each direction and backtracking when you hit a dead end.

Grid:
A B C E
S F C S
A D E E

Start at any cell and try to match letters of the word by moving up, down, left, or right.

Dry Run Walkthrough

Input: Grid: [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word: 'ABCCED'

Goal: Find if the word 'ABCCED' exists in the grid by moving to adjacent letters without reusing cells.

Step 1: Start at cell (0,0) with letter 'A', matches first letter of word

[A↑] B C E
S F C S
A D E E

Why: We need to find the first letter of the word to begin the search

Step 2: Move right to cell (0,1) with letter 'B', matches second letter

A [B↑] C E
S F C S
A D E E

Why: Next letter must be adjacent; right cell matches

Step 3: Move right to cell (0,2) with letter 'C', matches third letter

A B [C↑] E
S F C S
A D E E

Why: Continue matching letters in sequence

Step 4: Move down to cell (1,2) with letter 'C', matches fourth letter

A B C E
S F [C↑] S
A D E E

Why: Next letter adjacent below matches

Step 5: Move down to cell (2,2) with letter 'E', matches fifth letter

A B C E
S F C S
A D [E↑] E

Why: Continue matching letters

Step 6: Move left to cell (2,1) with letter 'D', matches sixth letter

A B C E
S F C S
A [D↑] E E

Why: Last letter matches, word found

Result:

Word found: A -> B -> C -> C -> E -> D

Annotated Code

DSA Go

package main

import "fmt"

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

	var backtrack func(r, c, index int) bool
	backtrack = func(r, c, index int) bool {
		if index == len(word) {
			return true // all letters matched
		}
		if r < 0 || c < 0 || r >= rows || c >= cols {
			return false // out of bounds
		}
		if visited[r][c] || board[r][c] != word[index] {
			return false // already used or letter mismatch
		}

		visited[r][c] = true // mark cell as used

		dirs := [][]int{{-1,0},{1,0},{0,-1},{0,1}} // up, down, left, right
		for _, d := range dirs {
			nr, nc := r + d[0], c + d[1]
			if backtrack(nr, nc, index+1) {
				return true // found path
			}
		}

		visited[r][c] = false // backtrack: unmark cell
		return false
	}

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

func main() {
	board := [][]byte{
		{'A','B','C','E'},
		{'S','F','C','S'},
		{'A','D','E','E'},
	}
	word := "ABCCED"
	fmt.Println(exist(board, word))
}

if index == len(word) { return true }

all letters matched, successful end condition

if r < 0 || c < 0 || r >= rows || c >= cols { return false }

stop if out of grid bounds

if visited[r][c] || board[r][c] != word[index] { return false }

skip if cell already used or letter does not match

visited[r][c] = true

mark current cell as used to avoid reuse

for _, d := range dirs { nr, nc := r + d[0], c + d[1]; if backtrack(nr, nc, index+1) { return true } }

try all four directions recursively to find next letter

visited[r][c] = false

backtrack by unmarking cell if path fails

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

start backtracking from every cell in the grid

Output

true

Complexity Analysis

Time: O(M * N * 4^L) because we start from each cell (M*N) and explore up to 4 directions for each letter in the word of length L

Space: O(L) for recursion stack and visited tracking, where L is the length of the word

vs Alternative: Brute force checking all paths without pruning would be much slower; backtracking prunes invalid paths early

Edge Cases

Empty grid

Returns false immediately because no letters to match

DSA Go

if r < 0 || c < 0 || r >= rows || c >= cols { return false }

Word longer than total cells

Returns false because word cannot fit

DSA Go

if index == len(word) { return true }

Word with repeated letters requiring careful path

Backtracking ensures cells are not reused incorrectly

DSA Go

if visited[r][c] || board[r][c] != word[index] { return false }

When to Use This Pattern

When you need to find a path matching a sequence in a grid with constraints on movement and no reuse, use backtracking to explore all valid paths efficiently.

Common Mistakes

Mistake: Not marking cells as visited, causing reuse of the same cell multiple times
Fix: Use a visited matrix to mark cells during the current path and unmark when backtracking

Mistake: Not checking boundary conditions before accessing grid cells
Fix: Always check if row and column indices are within grid bounds before accessing

Summary

Finds if a word exists in a grid by moving stepwise in four directions without reusing cells.

Use when searching for sequences in grids with adjacency and no repetition constraints.

The key is to try all paths and backtrack when a path does not lead to a solution.

Practice

1. What is the main purpose of using backtracking in a word search grid problem?

easy

A. To count the number of words in the grid

B. To sort the grid alphabetically

C. To explore all possible paths to find the word

D. To replace characters in the grid

Solution

1. Step 1: Understand backtracking in word search

   Backtracking tries all possible paths in the grid to find the target word by exploring neighbors recursively.

2. Step 2: Eliminate other options

   Sorting, counting, or replacing characters are unrelated to the search process using backtracking.

3. Final Answer:

   To explore all possible paths to find the word -> Option C

4. Quick Check:

   Backtracking = Explore paths [OK]

Hint: Backtracking means trying all paths until word found [OK]

Common Mistakes:

• Thinking backtracking sorts or modifies the grid
• Confusing backtracking with simple iteration
• Assuming backtracking counts words directly

2. Which of the following is the correct way to check if a position (row, col) is inside the grid in Go?

easy

A. if row > 0 && row <= len(grid) && col > 0 && col <= len(grid[0])

B. if row > 0 && row < len(grid) && col > 0 && col < len(grid[0])

C. if row >= 0 && row <= len(grid) && col >= 0 && col <= len(grid[0])

D. if row >= 0 && row < len(grid) && col >= 0 && col < len(grid[0])

Solution

1. Step 1: Understand grid indexing in Go

   Grid indices start at 0 and go up to length-1, so valid indices satisfy 0 <= row < len(grid) and 0 <= col < len(grid[0]).

2. Step 2: Check each option

   if row >= 0 && row < len(grid) && col >= 0 && col < len(grid[0]) correctly uses >= 0 and < length. Options A, C, D use incorrect bounds like > 0 or <= length which are off by one.

3. Final Answer:

   if row >= 0 && row < len(grid) && col >= 0 && col < len(grid[0]) -> Option D

4. Quick Check:

   Index check = if row >= 0 && row < len(grid) && col >= 0 && col < len(grid[0]) [OK]

Hint: Use zero-based indexing with < length for bounds [OK]

Common Mistakes:

• Using > 0 instead of >= 0 excludes first row/column
• Using <= length allows out-of-range index
• Confusing row and column lengths

3. What will be the output of the following Go code snippet for word search?

grid := [][]byte{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}
word := "ABCCED"
found := exist(grid, word)
fmt.Println(found)

func exist(board [][]byte, word string) bool {
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if backtrack(board, word, i, j, 0) {
                return true
            }
        }
    }
    return false
}

func backtrack(board [][]byte, word string, row, col, index int) bool {
    if index == len(word) {
        return true
    }
    if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) || board[row][col] != word[index] {
        return false
    }
    temp := board[row][col]
    board[row][col] = '#'
    found := backtrack(board, word, row+1, col, index+1) ||
             backtrack(board, word, row-1, col, index+1) ||
             backtrack(board, word, row, col+1, index+1) ||
             backtrack(board, word, row, col-1, index+1)
    board[row][col] = temp
    return found
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Understand the grid and word

   The grid contains the letters to form the word "ABCCED" starting at (0,0) moving right and down.

2. Step 2: Trace backtracking calls

   Backtracking explores neighbors and marks visited cells with '#'. The word "ABCCED" can be found following the path A->B->C->C->E->D.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Word found = true [OK]

Hint: Trace path letter by letter with backtracking [OK]

Common Mistakes:

• Not marking visited cells causing revisits
• Incorrect boundary checks causing false negatives
• Assuming word is not found without tracing path

4. The following Go code for word search returns false even when the word exists. What is the bug?

func backtrack(board [][]byte, word string, row, col, index int) bool {
    if index == len(word) {
        return true
    }
    if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) || board[row][col] != word[index] {
        return false
    }
    // Missing marking visited cell
    found := backtrack(board, word, row+1, col, index+1) ||
             backtrack(board, word, row-1, col, index+1) ||
             backtrack(board, word, row, col+1, index+1) ||
             backtrack(board, word, row, col-1, index+1)
    return found
}

medium

A. The function does not mark visited cells, causing revisits

B. The base case is incorrect and should return false

C. The boundary checks are missing

D. The word parameter is not passed correctly

Solution

1. Step 1: Analyze the backtrack function

   The function checks boundaries and matches characters but does not mark visited cells, so it can revisit the same cell multiple times.

2. Step 2: Understand the impact of missing visited marking

   Without marking visited cells, the search may loop or fail to find the word correctly because it revisits cells already used in the current path.

3. Final Answer:

   The function does not mark visited cells, causing revisits -> Option A

4. Quick Check:

   Missing visited marking = The function does not mark visited cells, causing revisits [OK]

Hint: Always mark visited cells to avoid revisiting [OK]

Common Mistakes:

• Ignoring visited marking causes infinite loops
• Misunderstanding base case logic
• Assuming boundary checks fix revisits

5. Given a grid and a list of words, how can you efficiently find all words present in the grid using backtracking? Choose the best approach.

hard

A. Run backtracking separately for each word on the entire grid

B. Build a Trie of words and use backtracking with pruning to find all words

C. Sort the grid and words alphabetically before searching

D. Replace all grid letters with '#' and then search

Solution

1. Step 1: Understand the problem of multiple words

   Searching each word separately is inefficient because it repeats similar searches multiple times.

2. Step 2: Use Trie with backtracking

   Building a Trie (prefix tree) of all words allows pruning paths early if no word matches, improving efficiency significantly.

3. Step 3: Eliminate incorrect options

   Sorting or replacing letters does not help search. Running backtracking separately is slow.

4. Final Answer:

   Build a Trie of words and use backtracking with pruning to find all words -> Option B

5. Quick Check:

   Trie + backtracking = efficient multi-word search [OK]

Hint: Use Trie to prune backtracking paths for multiple words [OK]

Common Mistakes:

• Searching each word independently wastes time
• Ignoring Trie data structure benefits
• Trying to sort grid which doesn't help search