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.