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

Concept Flow - Word Search in Grid Using Backtracking

Start at each cell in grid

↓

Check if cell matches first letter of word

Yes↓

Mark cell as visited

↓

Explore neighbors (up, down, left, right)

↓

For each neighbor: matches next letter?

↓

Recurse from neighbor

↓

If all letters matched

↓

Return True

↓

If no path found, backtrack and unmark cell

↓

Try next cell in grid

↓

If all cells tried, return False

The algorithm tries each cell as a start, then uses backtracking to explore neighbors matching the next letter, marking visited cells to avoid reuse, and backtracks if path fails.

Execution Sample

DSA Typescript

function exist(board: string[][], word: string): boolean {
  // Backtracking helper
  function backtrack(r: number, c: number, i: number): boolean {
    if (i === word.length) return true;
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
    if (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 < board.length; r++) {
    for (let c = 0; c < board[0].length; c++) {
      if (backtrack(r,c,0)) return true;
    }
  }
  return false;
}

This code checks if a word exists in a 2D grid by trying each cell as a start and using backtracking to explore neighbors matching the word letters.

Execution Table

Step	Operation	Current Cell (r,c)	Word Index i	Visited Cells	Action	Visual State
1	Start at cell	(0,0)	0	{}	Check if board[0][0] == word[0]	[A, B, C] [D, E, F] [G, H, I]
2	Match first letter	(0,0)	0	{}	board[0][0] == 'A' matches word[0] 'A'	[A, B, C] [D, E, F] [G, H, I]
3	Mark visited	(0,0)	0	{(0,0)}	Mark board[0][0] as visited '#'	[#, B, C] [D, E, F] [G, H, I]
4	Explore neighbors	(1,0)	1	{(0,0)}	Check board[1][0] == word[1] 'B'?	[#, B, C] [D, E, F] [G, H, I]
5	No match	(1,0)	1	{(0,0)}	board[1][0] == 'D' != 'B', backtrack	[#, B, C] [D, E, F] [G, H, I]
6	Explore neighbors	(0,1)	1	{(0,0)}	Check board[0][1] == word[1] 'B'?	[#, B, C] [D, E, F] [G, H, I]
7	Match	(0,1)	1	{(0,0),(0,1)}	Mark board[0][1] as visited '#'	[#, #, C] [D, E, F] [G, H, I]
8	Explore neighbors	(0,2)	2	{(0,0),(0,1)}	Check board[0][2] == word[2] 'C'?	[#, #, C] [D, E, F] [G, H, I]
9	Match	(0,2)	2	{(0,0),(0,1),(0,2)}	Mark board[0][2] as visited '#'	[#, #, #] [D, E, F] [G, H, I]
10	Word complete	N/A	3	{(0,0),(0,1),(0,2)}	All letters matched, return true	[#, #, #] [D, E, F] [G, H, I]
11	Backtrack	(0,2)	2	{(0,0),(0,1)}	Unmark board[0][2]	[#, #, C] [D, E, F] [G, H, I]
12	Backtrack	(0,1)	1	{(0,0)}	Unmark board[0][1]	[#, B, C] [D, E, F] [G, H, I]
13	Backtrack	(0,0)	0	{}	Unmark board[0][0]	[A, B, C] [D, E, F] [G, H, I]
14	Return	N/A	N/A	{}	Word found, exist() returns true	[A, B, C] [D, E, F] [G, H, I]

💡 Word found at step 10, backtracking to restore grid, then returning true.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 9	After Step 13	Final
r	N/A	0	0	0	0	N/A
c	N/A	0	1	2	0	N/A
i	0	0	1	2	0	N/A
Visited Cells	{}	{(0,0)}	{(0,0),(0,1)}	{(0,0),(0,1),(0,2)}	{}	{}
board state	[A,B,C],[D,E,F],[G,H,I]	[#,B,C],[D,E,F],[G,H,I]	[#,#,C],[D,E,F],[G,H,I]	[#,#,#],[D,E,F],[G,H,I]	[A,B,C],[D,E,F],[G,H,I]	[A,B,C],[D,E,F],[G,H,I]

Key Moments - 3 Insights

Why do we mark a cell as visited with '#' during backtracking?

Marking a cell as '#' prevents revisiting the same cell in the current path, avoiding infinite loops. See steps 3, 7, and 9 in execution_table where cells are marked before exploring neighbors.

Why do we unmark cells after exploring neighbors?

Unmarking restores the original letter so other paths can use the cell. This backtracking step is shown in steps 11, 12, and 13 where cells are unmarked after exploration.

What happens if the current cell letter does not match the word letter?

The search stops along that path immediately and backtracks. Step 5 shows this when board[1][0] 'D' does not match word letter 'B', so it backtracks.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, which cells are marked as visited?

A (0,0) and (0,1)

B (0,0) only

C (0,1) only

D (0,0), (0,1), and (0,2)

💡 Hint

Check the 'Visited Cells' column at step 7 in execution_table.

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

A Step 9

B Step 10

C Step 13

D Step 14

💡 Hint

Look for the step where 'All letters matched' is noted in the Action column.

If the first letter did not match at (0,0), what would the algorithm do next?

A Return true immediately

B Mark (0,0) as visited anyway

C Try next cell (0,1) as start

D Stop and return false

💡 Hint

Refer to the concept_flow where it tries each cell as a start if the current cell doesn't match.

Concept Snapshot

Word Search in Grid Using Backtracking:
- Try each cell as start
- If cell matches current letter, mark visited
- Recursively explore neighbors (up, down, left, right)
- Backtrack by unmarking if path fails
- Return true if all letters matched
- Return false if no path found

Full Transcript

This visualization shows how the word search algorithm uses backtracking to find a word in a grid. It starts from each cell, checks if the letter matches the first letter of the word, then marks the cell as visited to avoid reuse. It explores neighbors recursively for the next letters. If a path fails, it backtracks by unmarking cells. The execution table traces each step, showing visited cells and grid state. Key moments clarify why marking and unmarking are needed. The quiz tests understanding of visited cells, completion step, and next steps when letters don't match.

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