Word Search in Grid Using Backtracking in DSA Typescript

Mental Model

We try to find a word by moving step-by-step in the grid, checking each letter and going back if it doesn't fit.

Analogy: Imagine walking through a maze where each step must match a letter in the word. If you hit a dead end, you turn back and try a different path.

Grid:
A B C E
S F C S
A D E E

Word: SEE

Positions marked with ↑ show current search position.

Dry Run Walkthrough

Input: Grid: [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], Word: 'SEE'

Goal: Find if the word 'SEE' exists by moving horizontally or vertically in the grid.

Step 1: Start at grid[0][0] with letter 'A', does not match 'S', move to next cell

Grid positions checked: (0,0) 'A' ↑
No match, continue

Why: We need to find the first letter 'S' to start the search

Step 2: At grid[1][0] letter 'S' matches first letter of word, start backtracking

Grid positions checked: (1,0) 'S' ↑
Start matching 'S'

Why: Found first letter, now check neighbors for next letters

Step 3: Check neighbors of (1,0): (0,0), (2,0), (1,-1), (1,1). Only (0,0) 'A', (2,0) 'A' and (1,1) 'F' exist, neither matches 'E'

Neighbors checked: (0,0) 'A', (2,0) 'A', (1,1) 'F'
No match for second letter 'E'

Why: No valid next step, backtrack from (1,0)

Step 4: Continue scanning grid, find 'S' at (1,3), matches first letter

Grid positions checked: (1,3) 'S' ↑
Start matching 'S'

Why: Try another starting point for the word

Step 5: Check neighbors of (1,3): (0,3) 'E', (2,3) 'E', (1,2) 'C', (1,4) invalid

Neighbors: (0,3) 'E' ↑, (2,3) 'E' ↑
Both match second letter 'E'

Why: Two possible paths to continue

Step 6: Choose (0,3) 'E', check neighbors for third letter 'E': (0,2) 'C', (1,3) 'S', (0,4) invalid, (-1,3) invalid

Neighbors checked: no 'E' found for third letter

Why: Dead end, backtrack to (1,3)

Step 7: Choose (2,3) 'E', check neighbors for third letter 'E': (2,2) 'E', (1,3) 'S', (3,3) invalid, (2,4) invalid

Neighbor (2,2) 'E' ↑ matches third letter

Why: Found full word 'S'->'E'->'E'

Result:

Path found: (1,3) 'S' -> (2,3) 'E' -> (2,2) 'E'
Word 'SEE' exists in grid

Annotated Code

DSA Typescript

class WordSearch {
  private rows: number;
  private cols: number;

  constructor(private board: string[][], private word: string) {
    this.rows = board.length;
    this.cols = board[0].length;
  }

  exist(): boolean {
    for (let r = 0; r < this.rows; r++) {
      for (let c = 0; c < this.cols; c++) {
        if (this.backtrack(r, c, 0)) {
          return true;
        }
      }
    }
    return false;
  }

  private backtrack(r: number, c: number, index: number): boolean {
    if (index === this.word.length) return true; // all letters matched

    if (
      r < 0 || c < 0 || r >= this.rows || c >= this.cols ||
      this.board[r][c] !== this.word[index]
    ) {
      return false; // out of bounds or letter mismatch
    }

    const temp = this.board[r][c];
    this.board[r][c] = '#'; // mark visited

    // explore neighbors: up, down, left, right
    const found =
      this.backtrack(r - 1, c, index + 1) ||
      this.backtrack(r + 1, c, index + 1) ||
      this.backtrack(r, c - 1, index + 1) ||
      this.backtrack(r, c + 1, index + 1);

    this.board[r][c] = temp; // unmark
    return found;
  }
}

// Driver code
const board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E'],
];
const word = 'SEE';
const ws = new WordSearch(board, word);
console.log(ws.exist() ? 'Word found' : 'Word not found');

if (this.backtrack(r, c, 0)) { return true; }

start backtracking from each cell to find the word

if (index === this.word.length) return true;

all letters matched, word found

if (r < 0 || c < 0 || r >= this.rows || c >= this.cols || this.board[r][c] !== this.word[index]) return false;

stop if out of bounds or letter does not match

this.board[r][c] = '#';

mark current cell as visited to avoid reuse

const found = this.backtrack(...) || ...;

explore all four directions recursively

this.board[r][c] = temp;

unmark cell after exploring

Output

Word found

Complexity Analysis

Time: O(N * 3^L) where N is total cells and L is word length because each cell can start a search and each step explores up to 3 directions (excluding the previous cell).

Space: O(L) for recursion stack depth equal to word length.

vs Alternative: Naive search without backtracking would be inefficient and may revisit cells causing infinite loops; backtracking prunes invalid paths early.

Edge Cases

Empty grid

Returns false immediately as no cells to search

DSA Typescript

if (r < 0 || c < 0 || r >= this.rows || c >= this.cols || this.board[r][c] !== this.word[index]) return false;

Word longer than total cells

Returns false since word cannot fit

DSA Typescript

if (index === this.word.length) return true;

Word with repeated letters requiring careful path

Backtracking ensures correct path is found without reusing cells

DSA Typescript

this.board[r][c] = '#';

When to Use This Pattern

When you need to find a path matching a sequence in a grid with constraints on movement and no reuse of cells, use backtracking to explore all possible paths systematically.

Common Mistakes

Mistake: Not marking visited cells, causing revisiting and infinite loops
Fix: Mark cells as visited before recursive calls and unmark after to avoid reuse

Mistake: Not checking boundary conditions before accessing grid cells
Fix: Add boundary checks before accessing grid to prevent errors

Summary

Finds if a word exists in a grid by moving stepwise horizontally or vertically using backtracking.

Use when searching for sequences in grids where paths cannot reuse cells.

The key is to try all paths and backtrack when a path does not lead to a solution.

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