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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the current cell matches the current character of the word.

DSA Typescript

if (board[row][col] === [1]) {

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

Aword

Bword[index]

Cword.length

Dword[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Using word[0] instead of word[index]

Comparing with the whole word instead of a single character

We compare the board cell with the current character of the word at position 'index'.

2fill in blank

medium

Complete the code to mark the current cell as visited.

DSA Typescript

visited[row][col] = [1];

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

Afalse

Bnull

Ctrue

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited as false instead of true

Not marking visited at all

We mark the cell as visited by setting visited[row][col] to true.

3fill in blank

hard

Fix the error in the recursive call to explore neighbors by filling the correct row offset.

DSA Typescript

if (dfs(board, word, row + [1], col, index + 1, visited)) {

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

A0

Bindex

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 does not move to a neighbor

Using index instead of a row offset

To move down, we add 1 to the row index.

4fill in blank

hard

Fill both blanks to check boundaries and if the cell is already visited.

DSA Typescript

if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || visited[[1]][[2]]) { return false; }

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

Arow

Bcol

Cindex

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using index or word instead of row and col

Checking visited outside the board boundaries

We check if the cell at visited[row][col] is already visited.

5fill in blank

hard

Fill all three blanks to explore all four directions (up, down, left, right) in the DFS.

DSA Typescript

return dfs(board, word, row + [1], col + [2], index + 1, visited) || dfs(board, word, row + [3], col, index + 1, visited) || dfs(board, word, row, col + 1, index + 1, visited) || dfs(board, word, row, col - 1, index + 1, visited);

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

A1

B-1

C0

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing row and column offsets

Using index instead of numeric offsets

We move down (row + 1), up (row - 1), right (col + 1), and left (col - 1). Here blanks correspond to row offset for down (1), col offset for left/right (0), and row offset for up (-1).

Practice

1. What is the main purpose of backtracking in the Word Search problem on a grid?

easy

A. To sort the grid alphabetically

B. To explore all possible paths to find the word

C. To count the number of words in the grid

D. To replace characters in the grid

Solution

1. Step 1: Understand backtracking role

   Backtracking tries all possible paths from each cell to find the target word.

2. Step 2: Eliminate other options

   Sorting, counting, or replacing characters are unrelated to backtracking in word search.

3. Final Answer:

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

4. Quick Check:

   Backtracking = Explore paths [OK]

Hint: Backtracking means trying all paths step-by-step [OK]

Common Mistakes:

• Thinking backtracking sorts or counts
• Confusing backtracking with simple search
• Ignoring path exploration in grid

2. Which of the following TypeScript function signatures correctly represents a backtracking helper for word search in a grid?

easy

A. function backtrack(grid: string[][], word: string, row: number, col: number, index: number): boolean

B. function backtrack(grid: number[], word: string): void

C. function backtrack(word: string, grid: string[][]): number

D. function backtrack(grid: string[][], word: string): string

Solution

1. Step 1: Identify correct parameters

   The helper needs the grid, the word, current position (row, col), and index in word to track progress.

2. Step 2: Check return type

   It returns boolean to indicate if word is found along the path.

3. Final Answer:

   function backtrack(grid: string[][], word: string, row: number, col: number, index: number): boolean -> Option A

4. Quick Check:

   Correct params and boolean return = function backtrack(grid: string[][], word: string, row: number, col: number, index: number): boolean [OK]

Hint: Helper needs grid, position, index, returns boolean [OK]

Common Mistakes:

• Missing row and col parameters
• Wrong return type (void or number)
• Incorrect parameter order

3. What will be the output of the following TypeScript code snippet?

const board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
];

function exist(board: string[][], word: string): boolean {
  const rows = board.length;
  const cols = board[0].length;

  function backtrack(r: number, c: number, i: number): boolean {
    if (i === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[i]) return false;

    const temp = board[r][c];
    board[r][c] = '#';

    const 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 (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (backtrack(r, c, 0)) return true;
    }
  }
  return false;
}

console.log(exist(board, 'ABCCED'));

medium

A. SyntaxError

B. false

C. true

D. undefined

Solution

1. Step 1: Understand the board and word

   The word 'ABCCED' can be found by moving right and down in the grid starting at (0,0).

2. Step 2: Trace backtracking calls

   Backtracking marks visited cells and explores neighbors; it finds the word successfully and returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Word found in grid = true [OK]

Hint: Trace path for word in grid; returns true if found [OK]

Common Mistakes:

• Assuming word is not found
• Ignoring visited cell marking
• Confusing return values

4. Identify the bug in this backtracking function for word search and select the fix:

function backtrack(r: number, c: number, i: number): boolean {
  if (i === word.length) return true;
  if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
  if (board[r][c] !== word[i]) return false;

  board[r][c] = '#';

  const 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);

  return found;
}

medium

A. Restore board[r][c] to original after recursive calls

B. Change base case to i > word.length

C. Remove boundary checks

D. Return false immediately after marking cell

Solution

1. Step 1: Identify missing restoration

   The function marks board[r][c] as '#' but never restores it after recursion, corrupting the grid.

2. Step 2: Fix by restoring cell

   After recursive calls, restore board[r][c] to original character to allow other paths to use it.

3. Final Answer:

   Restore board[r][c] to original after recursive calls -> Option A

4. Quick Check:

   Restore cell after recursion = Restore board[r][c] to original after recursive calls [OK]

Hint: Always restore grid cell after backtracking recursion [OK]

Common Mistakes:

• Forgetting to restore visited cells
• Changing base case incorrectly
• Removing necessary boundary checks

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

hard

A. Replace all grid letters with '#' before searching

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

C. Sort words alphabetically and search only the first word

D. Use a Trie to store words and backtrack once to find all matches

Solution

1. Step 1: Understand inefficiency of separate searches

   Running backtracking for each word separately repeats work and is slow for many words.

2. Step 2: Use Trie with backtracking

   Building a Trie of all words allows one backtracking pass to find all words efficiently by pruning invalid paths early.

3. Final Answer:

   Use a Trie to store words and backtrack once to find all matches -> Option D

4. Quick Check:

   Trie + single backtracking = efficient search [OK]

Hint: Combine Trie with backtracking for multiple words [OK]

Common Mistakes:

• Searching each word separately wastes time
• Sorting words doesn't help search
• Modifying grid destructively before search