Word Search in Grid Using Backtracking in DSA Javascript - Execution Trace

Concept Flow - Word Search in Grid Using Backtracking

Start at each cell in grid

↓

Check if cell matches first letter

Yes↓

Mark cell visited

↓

Explore neighbors (up, down, left, right)

↓

Check next letter match

Yes↓

Repeat until word complete

No↓

Backtrack: unmark cell

↓

Try next neighbor or next start cell

↓

Word found?

↓

Return True

Start from each cell, check if it matches the first letter. If yes, mark visited and explore neighbors recursively for next letters. Backtrack if no match. Repeat until word is found or all options exhausted.

Execution Sample

DSA Javascript

function exist(board, word) {
  // Start from each cell
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (backtrack(i, j, 0)) return true;
    }
  }
  return false;
}

function backtrack(i, j, wordIndex) {
  if (wordIndex === word.length) return true;
  if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
  if (board[i][j] !== word[wordIndex]) return false;

  const temp = board[i][j];
  board[i][j] = '#'; // mark visited

  const found = backtrack(i + 1, j, wordIndex + 1) ||
                backtrack(i - 1, j, wordIndex + 1) ||
                backtrack(i, j + 1, wordIndex + 1) ||
                backtrack(i, j - 1, wordIndex + 1);

  board[i][j] = temp; // unmark
  return found;
}

Checks if the word exists in the grid by trying each cell as a start and using backtracking.

Execution Table

Step	Operation	Current Position (i,j)	Word Index	Visited Cells	Visual Grid State
1	Start at cell	(0,0)	0	{}	[A, B, C] [D, E, F] [G, H, I]
2	Check letter match	(0,0)	0	{}	[A, B, C] [D, E, F] [G, H, I]
3	Letter matches 'A'	(0,0)	0	{(0,0)}	[*A*, B, C] [D, E, F] [G, H, I]
4	Explore neighbors	(0,1)	1	{(0,0)}	[*A*, B, C] [D, E, F] [G, H, I]
5	Letter matches 'B'	(0,1)	1	{(0,0),(0,1)}	[*A*, *B*, C] [D, E, F] [G, H, I]
6	Explore neighbors	(0,2)	2	{(0,0),(0,1)}	[*A*, *B*, C] [D, E, F] [G, H, I]
7	Letter matches 'C'	(0,2)	2	{(0,0),(0,1),(0,2)}	[*A*, *B*, *C*] [D, E, F] [G, H, I]
8	Word complete	(0,2)	3	{(0,0),(0,1),(0,2)}	[*A*, *B*, *C*] [D, E, F] [G, H, I]
9	Return True	-	-	-	-

💡 Word found at step 8, backtracking stops and returns true.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
i	0	0	0	0	0
j	0	0	1	2	2
wordIndex	0	0	1	2	3
visited	{}	{(0,0)}	{(0,0),(0,1)}	{(0,0),(0,1),(0,2)}	{(0,0),(0,1),(0,2)}

Key Moments - 3 Insights

Why do we mark a cell as visited before exploring neighbors?

Marking prevents revisiting the same cell in the current path, avoiding infinite loops. See step 3 where (0,0) is marked visited before exploring neighbors in step 4.

What happens if a neighbor cell does not match the next letter?

Backtracking occurs: the cell is unmarked and the search tries other neighbors or backtracks further. This is implied between steps 6 and 7 if a neighbor fails.

Why do we return true immediately when the word is complete?

Because the goal is to find if the word exists anywhere. Once all letters match (step 8), no further search is needed.

Visual Quiz - 3 Questions

Look at the execution table, what is the visited set after step 5?

A {}

B {(0,0)}

C {(0,0),(0,1)}

D {(0,0),(0,1),(0,2)}

💡 Hint

Check the 'Visited Cells' column at step 5 in the execution table.

At which step does the algorithm confirm the word is found?

A Step 6

B Step 8

C Step 7

D Step 9

💡 Hint

Look for the step where 'Word complete' is noted in the 'Operation' column.

If the first cell (0,0) did not match the first letter, what would happen?

A The algorithm would try the next cell (0,1) as start.

B The algorithm would return true immediately.

C The algorithm would mark (0,0) visited anyway.

D The algorithm would stop searching.

💡 Hint

Refer to the 'Start at each cell' step in the concept flow and execution table step 1.

Concept Snapshot

Word Search in Grid Using Backtracking:
- Start from each cell in the grid
- Check if cell matches current word letter
- Mark cell visited to avoid reuse
- Recursively explore neighbors (up, down, left, right)
- Backtrack if no match found
- Return true if full word matched, else false

Full Transcript

This concept shows how to find a word in a grid by starting from each cell and using backtracking. We check if the current cell matches the current letter of the word. If yes, we mark it visited and explore neighbors for the next letter. If a path fails, we backtrack by unmarking the cell and trying other neighbors. The process repeats until the word is found or all options are exhausted. The execution table traces each step, showing positions, visited cells, and the grid state. Key moments clarify why marking visited is important, how backtracking works, and when the search stops. The visual quiz tests understanding of visited sets, completion step, and start cell behavior.

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