Word Search in Grid Using Backtracking in DSA Go - Execution Trace

Concept Flow - Word Search in Grid Using Backtracking

Start at each cell in grid

↓

Check if cell matches first letter of word

↓

If match, start backtracking

↓

Explore neighbors (up, down, left, right)

↓

Check if next letter matches and not visited

↓

If all letters matched

→Return True

↓

If no match, backtrack and try other paths

↓

If all cells tried and no match

→Return False

The algorithm tries each cell as a start, then uses backtracking to explore neighbors matching the word letters step-by-step.

Execution Sample

DSA Go

func exist(board [][]byte, word string) bool {
  // Try each cell
  for i := range board {
    for j := range board[0] {
      if backtrack(board, word, 0, i, j) {
        return true
      }
    }
  }
  return false
}

This code tries each cell in the grid as a starting point and calls backtracking to find the word.

Execution Table

Step	Operation	Current Position (i,j)	Word Index	Visited Cells	Action	Visual State
1	Start at cell	(0,0)	0	{}	Check if board[0][0] == word[0]	Grid with no visited cells
2	Match first letter	(0,0)	0	{(0,0)}	Mark visited, move to neighbors	Visited: (0,0)
3	Explore neighbor	(0,1)	1	{(0,0),(0,1)}	Check if board[0][1] == word[1]	Visited: (0,0) -> (0,1)
4	No match	(0,1)	1	{(0,0)}	Backtrack, unmark (0,1)	Visited: (0,0)
5	Explore neighbor	(1,0)	1	{(0,0),(1,0)}	Check if board[1][0] == word[1]	Visited: (0,0) -> (1,0)
6	Match	(1,0)	1	{(0,0),(1,0)}	Mark visited, move to next letter	Visited: (0,0) -> (1,0)
7	Explore neighbor	(2,0)	2	{(0,0),(1,0),(2,0)}	Check if board[2][0] == word[2]	Visited: (0,0) -> (1,0) -> (2,0)
8	Match	(2,0)	2	{(0,0),(1,0),(2,0)}	Mark visited, move to next letter	Visited: (0,0) -> (1,0) -> (2,0)
9	Explore neighbor	(2,1)	3	{(0,0),(1,0),(2,0),(2,1)}	Check if board[2][1] == word[3]	Visited: (0,0) -> (1,0) -> (2,0) -> (2,1)
10	Match	(2,1)	3	{(0,0),(1,0),(2,0),(2,1)}	All letters matched, return True	Visited path forms word
11	Return	-	-	-	Word found, stop search	Final path highlighted
12	Exit	-	-	-	No more cells to try	Search complete

💡 Word found at step 10, backtracking returns true and search stops

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 9	Final
Current Position (i,j)	-	(0,0)	(1,0)	(2,0)	(2,1)	-
Word Index	0	0	1	2	3	-
Visited Cells	{}	{(0,0)}	{(0,0),(1,0)}	{(0,0),(1,0),(2,0)}	{(0,0),(1,0),(2,0),(2,1)}	-

Key Moments - 3 Insights

Why do we mark cells as visited and then unmark them during backtracking?

We mark cells to avoid revisiting the same cell in the current path (see steps 2 and 4). If a path fails, we unmark to allow other paths to use that cell (step 4 backtracks).

Why do we check neighbors only in four directions (up, down, left, right)?

The problem defines adjacency as horizontal or vertical neighbors only, so diagonals are not considered (see step 3 exploring neighbors).

What happens if the first letter does not match at a cell?

We skip backtracking from that cell and move to the next cell (step 1 checks match; if no match, continue loop).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the current word index?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Word Index' column at step 5 in the execution_table

At which step does the algorithm find that all letters are matched?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look for the step where 'All letters matched' is mentioned in the 'Action' column

If the cell at (0,1) matched the second letter, what would happen at step 4?

A Backtracking would continue exploring neighbors from (0,1)

B Backtracking would stop immediately

C Cell (0,1) would be skipped

D The algorithm would restart from (0,0)

💡 Hint

Step 4 shows backtracking unmarking (0,1) because it did not match; if it matched, exploration continues

Concept Snapshot

Word Search Backtracking:
- Start from each cell
- Match letters step-by-step
- Mark visited cells to avoid reuse
- Explore neighbors (up, down, left, right)
- Backtrack if path fails
- Return true if full word matched

Full Transcript

This visualization shows how the word search algorithm uses backtracking to find a word in a grid. It starts from each cell and checks if the first letter matches. If yes, it marks the cell visited and explores neighbors for the next letter. If a neighbor matches, it continues deeper. If no match is found, it backtracks by unmarking the cell and tries other paths. The process repeats until the word is found or all cells are tried. The execution table tracks each step, current position, visited cells, and actions. Key moments clarify why marking visited cells is important and why only four directions are checked. The quiz tests understanding of the steps and backtracking behavior.

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