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.