Word Search in Grid Using Backtracking in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Search Result for Simple Grid

What is the output of the following Go code that checks if the word "CAT" exists in the given grid using backtracking?

DSA Go

package main
import "fmt"

func exist(board [][]byte, word string) bool {
    rows := len(board)
    cols := len(board[0])
    var backtrack func(r, c, i int) bool
    backtrack = func(r, c, i int) bool {
        if i == len(word) {
            return true
        }
        if r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word[i] {
            return false
        }
        temp := board[r][c]
        board[r][c] = '#'
        found := backtrack(r+1, c, i+1) || backtrack(r-1, c, i+1) || backtrack(r, c+1, i+1) || backtrack(r, c-1, i+1)
        board[r][c] = temp
        return found
    }
    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{
        {'C', 'A', 'T'},
        {'X', 'Y', 'Z'},
        {'A', 'B', 'C'},
    }
    fmt.Println(exist(board, "CAT"))
}

A true

B false

C SyntaxError

D runtime error

💡 Hint

Trace the path of letters C -> A -> T in the grid.

The word "CAT" can be found starting at board[0][0] moving right to board[0][1] and then board[0][2]. The backtracking function returns true.

❓ Predict Output

intermediate

Output of Word Search for Word Not Present

What is the output of the following Go code that checks if the word "DOG" exists in the given grid using backtracking?

DSA Go

package main
import "fmt"

func exist(board [][]byte, word string) bool {
    rows := len(board)
    cols := len(board[0])
    var backtrack func(r, c, i int) bool
    backtrack = func(r, c, i int) bool {
        if i == len(word) {
            return true
        }
        if r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word[i] {
            return false
        }
        temp := board[r][c]
        board[r][c] = '#'
        found := backtrack(r+1, c, i+1) || backtrack(r-1, c, i+1) || backtrack(r, c+1, i+1) || backtrack(r, c-1, i+1)
        board[r][c] = temp
        return found
    }
    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{
        {'C', 'A', 'T'},
        {'X', 'Y', 'Z'},
        {'A', 'B', 'C'},
    }
    fmt.Println(exist(board, "DOG"))
}

A true

B SyntaxError

C runtime error

D false

💡 Hint

Check if all letters D, O, G appear connected in the grid.

The word "DOG" cannot be found anywhere in the grid, so the function returns false.

🧠 Conceptual

advanced

Why Mark Visited Cells in Word Search Backtracking?

In the backtracking approach for word search in a grid, why do we temporarily mark a cell as visited (e.g., replacing its letter with '#') during the search?

A To permanently remove the letter from the grid after checking it once

B To avoid revisiting the same cell in the current search path and prevent cycles

C To speed up the search by sorting the grid letters

D To mark cells that do not contain any letter from the word

💡 Hint

Think about what happens if you revisit the same cell multiple times in one word search path.

Marking a cell as visited prevents the algorithm from using the same cell multiple times in the current path, which avoids infinite loops and incorrect matches.

🔧 Debug

advanced

Identify the Bug in Word Search Backtracking Code

What error will the following Go code produce when running the word search backtracking function?

DSA Go

package main
import "fmt"

func exist(board [][]byte, word string) bool {
    rows := len(board)
    cols := len(board[0])
    var backtrack func(r, c, i int) bool
    backtrack = func(r, c, i int) bool {
        if i == len(word) {
            return true
        }
        if r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word[i] {
            return false
        }
        temp := board[r][c]
        board[r][c] = '#'
        found := backtrack(r+1, c, i+1) || backtrack(r-1, c, i+1) || backtrack(r, c+1, i+1) || backtrack(r, c-1, i+1)
        // Missing restoration of board[r][c]
        return found
    }
    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{
        {'C', 'A', 'T'},
        {'X', 'Y', 'Z'},
        {'A', 'B', 'C'},
    }
    fmt.Println(exist(board, "CAT"))
}

A The code prints false because the board is corrupted during backtracking

B The code runs correctly and prints true

C Compilation error due to missing return statement

D Runtime panic due to index out of range

💡 Hint

Check if the board is restored after marking a cell visited.

The code does not restore the original letter after marking it as '#', so subsequent searches see corrupted board cells and fail to find the word.

🚀 Application

expert

Count All Occurrences of a Word in Grid Using Backtracking

Given a grid and a word, which approach correctly counts all distinct occurrences of the word in the grid using backtracking?

A Use backtracking but permanently remove letters from the grid after first match

B Use backtracking without marking visited cells, increment count when full word matched

C Use backtracking from each cell, mark visited cells temporarily, increment count when full word matched, and restore cells after recursion

D Use BFS to find the word once and return 1 if found, else 0

💡 Hint

Think about how to avoid counting overlapping or invalid paths multiple times.

Marking visited cells temporarily ensures paths do not reuse the same cell. Restoring cells allows counting all distinct occurrences. BFS or permanent removal do not correctly count all occurrences.

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