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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Search Result for Simple Grid

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

DSA Javascript

const board = [
  ['C', 'A', 'T'],
  ['X', 'Y', 'Z'],
  ['A', 'B', 'C']
];

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));

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

    visited[r][c] = true;
    const res = backtrack(r + 1, c, index + 1) ||
                backtrack(r - 1, c, index + 1) ||
                backtrack(r, c + 1, index + 1) ||
                backtrack(r, c - 1, index + 1);
    visited[r][c] = false;
    return res;
  }

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

console.log(exist(board, "CAT"));

A true

B false

C SyntaxError

D TypeError

💡 Hint

Think about whether the letters C, A, T appear consecutively in the grid horizontally or vertically.

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

❓ Predict Output

intermediate

Output of Word Search for Word Not Present

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

DSA Javascript

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

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));

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

    visited[r][c] = true;
    const res = backtrack(r + 1, c, index + 1) ||
                backtrack(r - 1, c, index + 1) ||
                backtrack(r, c + 1, index + 1) ||
                backtrack(r, c - 1, index + 1);
    visited[r][c] = false;
    return res;
  }

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

console.log(exist(board, "ODG"));

A false

B true

C ReferenceError

D RangeError

💡 Hint

Check if the letters O, D, G appear consecutively in the grid horizontally or vertically without reusing cells.

The word "ODG" is not present in the grid in consecutive adjacent cells in the required order, so the function returns false.

❓ Predict Output

intermediate

Output of Word Search for Word "GDO" Not Present

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

DSA Javascript

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

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));

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

    visited[r][c] = true;
    const res = backtrack(r + 1, c, index + 1) ||
                backtrack(r - 1, c, index + 1) ||
                backtrack(r, c + 1, index + 1) ||
                backtrack(r, c - 1, index + 1);
    visited[r][c] = false;
    return res;
  }

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

console.log(exist(board, "GDO"));

A true

B false

C SyntaxError

D TypeError

💡 Hint

Check if the letters G, D, O appear consecutively in the grid horizontally or vertically without reusing cells.

The word "GDO" is not present in the grid in consecutive adjacent cells in the required order, so the function returns false.

🔧 Debug

advanced

Identify the Bug in Word Search Backtracking Code

The following code is intended to find if a word exists in a grid using backtracking. However, it sometimes returns incorrect results. What is the bug?

DSA Javascript

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));

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

    visited[r][c] = true;
    const res = backtrack(r + 1, c, index + 1) ||
                backtrack(r - 1, c, index + 1) ||
                backtrack(r, c + 1, index + 1) ||
                backtrack(r, c - 1, index + 1);
    visited[r][c] = false;
    return res;
  }

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

A The function does not check diagonal neighbors which is required for word search.

B The base case should check if index > word.length instead of index === word.length.

C The visited array is not reset to false after backtracking, causing incorrect reuse of cells.

D The function should use a global visited array instead of creating a new one each call.

💡 Hint

Think about what happens after exploring one path and backtracking to try another.

The visited cells must be marked as unvisited after exploring a path to allow other paths to use those cells. Without resetting visited[r][c] to false, the function wrongly blocks valid paths.

🚀 Application

expert

Minimum Steps to Form Word in Grid with Backtracking

Given a grid and a word, you want to find the minimum number of steps to form the word by moving horizontally or vertically to adjacent cells. Each step moves to one adjacent cell. You can start at any cell matching the first letter. Which approach best solves this problem?

A Use greedy approach by always moving to the closest next letter without backtracking.

B Use backtracking with pruning to explore all paths and track minimum steps.

C Use dynamic programming to store minimum steps for each prefix of the word at each cell.

D Use breadth-first search (BFS) from all starting points simultaneously to find shortest path.

💡 Hint

Think about shortest path in a grid and how to explore multiple starting points efficiently.

BFS is suitable for shortest path problems in grids. Starting BFS from all cells matching the first letter simultaneously finds the minimum steps to form the word efficiently.

Practice

1. What is the main purpose of using backtracking in a word search grid problem?

easy

A. To sort the grid alphabetically

B. To count the number of words in the grid

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 words, or replacing characters are not related to backtracking's purpose in this problem.

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 step-by-step [OK]

Common Mistakes:

• Thinking backtracking sorts or modifies the grid
• Confusing backtracking with simple searching
• 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 boundaries in JavaScript?

easy

A. if (row > 0 && row <= grid.length && col > 0 && col <= grid[0].length)

B. if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length)

C. if (row >= 0 && row <= grid.length && col >= 0 && col <= grid[0].length)

D. if (row > 0 && row < grid.length && col > 0 && col < grid[0].length)

Solution

1. Step 1: Understand grid indexing

   Grid rows and columns start at 0 and go up to length - 1, so valid indices satisfy 0 <= row < length.

2. Step 2: Check each option

   if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length) correctly uses >= 0 and < length. Others use > 0 or <= length, which are incorrect for zero-based indexing.

3. Final Answer:

   if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length) -> Option B

4. Quick Check:

   Check boundaries with >=0 and < length [OK]

Hint: Use zero-based indexing: start at 0, less than length [OK]

Common Mistakes:

• Using > 0 excludes first row/column
• Using <= length allows out-of-bound index
• Confusing inclusive and exclusive bounds

3. What will be the output of the following code snippet when searching for the word "CAT" in the given grid?

const grid = [
  ['C', 'A', 'T'],
  ['A', 'T', 'C'],
  ['T', 'C', 'A']
];

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));

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

    visited[r][c] = true;
    const res = backtrack(r + 1, c, index + 1) || backtrack(r - 1, c, index + 1) || backtrack(r, c + 1, index + 1) || backtrack(r, c - 1, index + 1);
    visited[r][c] = false;
    return res;
  }

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

console.log(exist(grid, "CAT"));

medium

A. true

B. false

C. SyntaxError

D. undefined

Solution

1. Step 1: Trace the backtracking search for "CAT"

   The word "CAT" can be found starting at grid[0][0] = 'C', then right to 'A', then right to 'T'. The function returns true.

2. Step 2: Confirm no errors and correct return

   The code correctly marks visited cells and explores neighbors. It returns true when the word is found.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Word "CAT" found in grid = true [OK]

Hint: Check neighbors recursively for each letter [OK]

Common Mistakes:

• Ignoring visited array causing infinite loops
• Not checking all directions
• Assuming word must be in a straight line only

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

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

  visited[r][c] = true;
  const res = backtrack(r + 1, c, index + 1) || backtrack(r - 1, c, index + 1) || backtrack(r, c + 1, index + 1) || backtrack(r, c - 1, index + 1);
  return res;
}

medium

A. Change the base case to index > word.length

B. Remove the boundary checks for r and c

C. Remove the visited array usage completely

D. Add visited[r][c] = false after recursive calls to unmark

Solution

1. Step 1: Identify missing backtracking step

   The function marks visited[r][c] = true but never resets it to false after recursion, causing wrong results.

2. Step 2: Fix by unmarking visited after recursion

   Adding visited[r][c] = false after recursive calls allows other paths to use this cell again.

3. Final Answer:

   Add visited[r][c] = false after recursive calls to unmark -> Option D

4. Quick Check:

   Unmark visited after recursion to backtrack [OK]

Hint: Always reset visited after recursion to explore other paths [OK]

Common Mistakes:

• Forgetting to unmark visited cells
• Removing boundary checks causing errors
• Changing base case incorrectly

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

hard

A. Use a Trie (prefix tree) to reduce repeated searches and backtrack once

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

C. Sort the words and grid alphabetically before searching

D. Replace all grid letters with the first letter of each word before searching

Solution

1. Step 1: Understand inefficiency of separate searches

   Running backtracking for each word separately repeats many searches, wasting time.

2. Step 2: Use Trie to optimize search

   Building a Trie of all words allows backtracking once, pruning paths that don't match any prefix, improving efficiency.

3. Final Answer:

   Use a Trie (prefix tree) to reduce repeated searches and backtrack once -> Option A

4. Quick Check:

   Trie + backtracking = efficient multi-word search [OK]

Hint: Use Trie to share prefixes and avoid repeated searches [OK]

Common Mistakes:

• Searching each word independently causing slow performance
• Sorting grid or words doesn't help search
• Modifying grid letters breaks correctness