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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Search Result

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

DSA Typescript

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

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

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

    const found = backtrack(r + 1, c, index + 1) ||
                  backtrack(r - 1, c, index + 1) ||
                  backtrack(r, c + 1, index + 1) ||
                  backtrack(r, c - 1, index + 1);

    board[r][c] = temp;
    return found;
  }

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

const grid = [
  ['C', 'A', 'T'],
  ['X', 'Z', 'Y'],
  ['B', 'O', 'T']
];
console.log(exist(grid, "CAT"));

A false

B true

C SyntaxError

D TypeError

💡 Hint

Think about whether the word "CAT" can be found by moving horizontally or vertically in the grid.

The word "CAT" is found in the first row of the grid from left to right, so the function returns true.

🧠 Conceptual

intermediate

Understanding Backtracking in Word Search

Which of the following best describes why backtracking is used in the word search algorithm?

A It sorts the grid to find the word faster.

B It uses a queue to explore all neighbors simultaneously.

C It tries all possible paths to find the word, undoing steps when a path fails.

D It stores all words in a hash map for quick lookup.

💡 Hint

Backtracking involves exploring and undoing choices.

Backtracking explores all possible paths and reverts changes when a path does not lead to the solution.

❓ Predict Output

advanced

Output of Word Search with Overlapping Paths

What is the output of this code when searching for the word "ABCB" in the given grid?

DSA Typescript

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

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

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

    const found = backtrack(r + 1, c, index + 1) ||
                  backtrack(r - 1, c, index + 1) ||
                  backtrack(r, c + 1, index + 1) ||
                  backtrack(r, c - 1, index + 1);

    board[r][c] = temp;
    return found;
  }

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

const grid = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
];
console.log(exist(grid, "ABCB"));

A false

B SyntaxError

C RuntimeError

D true

💡 Hint

The word "ABCB" requires reusing the same cell which is not allowed.

The algorithm prevents revisiting the same cell in the current path, so "ABCB" cannot be formed.

🔧 Debug

advanced

Identify the Bug in Word Search Code

What error will this code produce when searching for the word "DOG" in the grid?

DSA Typescript

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

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

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

    const found = backtrack(r + 1, c, index + 1) ||
                  backtrack(r - 1, c, index + 1) ||
                  backtrack(r, c + 1, index + 1) ||
                  backtrack(r, c - 1, index + 1);

    board[r][c] = temp;
    return found;
  }

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

const grid = [
  ['D', 'O', 'G'],
  ['X', 'Y', 'Z'],
  ['A', 'B', 'C']
];
console.log(exist(grid, "DOG"));

A false

B true

C SyntaxError

D IndexError

💡 Hint

Check the boundary conditions in the if statement inside backtrack.

The conditions 'r > rows' and 'c > cols' allow out-of-bound indices causing an IndexError.

🧠 Conceptual

expert

Time Complexity of Word Search Backtracking

What is the worst-case time complexity of the backtracking algorithm for word search in a grid of size m x n and a word of length k?

A O(m * n * 4^k)

B O(m * n * k)

C O(k^2)

D O(m^k * n^k)

💡 Hint

Each step can explore up to 4 directions for each character in the word.

At each of the k characters, the algorithm explores up to 4 directions from each cell, and there are m*n starting cells.

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