Word Search in Grid Using Backtracking in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start the search from the first cell in the grid.

DSA Go

for i := 0; i < len(board); i++ {
    for j := 0; j < len(board[0]); j++ {
        if board[i][j] == word[[1]] {
            if backtrack(board, word, i, j, 0) {
                return true
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

Alen(word)

B1

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 0 as the starting index.

Using len(word) which is out of range.

The search starts by matching the first character of the word, which is at index 0.

2fill in blank

medium

Complete the code to mark the current cell as visited during backtracking.

DSA Go

temp := board[i][j]
board[i][j] = [1]

// backtracking calls here

board[i][j] = temp

Drag options to blanks, or click blank then click option'

A'*'

B'#'

C' '

D'0'

Attempts:

3 left

💡 Hint

Common Mistakes

Using a space character which might be confusing.

Using '0' which could be a valid board character.

Marking the cell with '#' indicates it is visited and prevents revisiting during the current path.

3fill in blank

hard

Fix the error in the recursive backtracking call to check all four directions.

DSA Go

directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for _, dir := range directions {
    x, y := i+dir[0], j+dir[[1]]
    if backtrack(board, word, x, y, index+1) {
        return true
    }
}

Drag options to blanks, or click blank then click option'

A0

B3

C2

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for both indices causing incorrect coordinates.

Using 2 or 3 which are out of range.

The second element of dir is at index 1, representing the column offset.

4fill in blank

hard

Fill both blanks to check if the current position is valid inside the grid.

DSA Go

if i < 0 || i >= [1] || j < 0 || j >= [2] {
    return false
}

Drag options to blanks, or click blank then click option'

Alen(board)

Blen(board[0])

Clen(word)

Dlen(board) - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(word) which is unrelated to grid size.

Using len(board) - 1 without proper comparison.

The row index i must be within 0 and len(board)-1, and column index j within 0 and len(board[0])-1.

5fill in blank

hard

Fill all three blanks to complete the backtracking function signature and base case.

DSA Go

func backtrack(board [][]byte, word string, i, j, [1] int) bool {
    if [2] == len(word) {
        return [3]
    }
    // rest of the code
}

Drag options to blanks, or click blank then click option'

Aindex

Ctrue

Di

Efalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'i' instead of 'index' for the position.

Returning false instead of true at base case.

The function uses 'index' to track the current character position; when index equals word length, the word is found, so return true.

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