Word Search in Grid Using Backtracking in DSA Typescript - Time & Space Complexity

Time Complexity: Word Search in Grid Using Backtracking

O(N * 4^M)

Understanding Time Complexity

We want to understand how the time needed to find a word in a grid grows as the grid and word sizes increase.

Specifically, how does the search time change when we try all possible paths to match the word?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function exist(board: string[][], word: string): boolean {
  const rows = board.length;
  const cols = board[0].length;

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

    const temp = board[r][c];
    board[r][c] = '#';

    const found = backtrack(r+1, c, index+1) || backtrack(r-1, c, index+1) || backtrack(r, c+1, index+1) || backtrack(r, c-1, index+1);

    board[r][c] = temp;
    return found;
  }

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

This code tries to find the given word in the grid by exploring all possible paths using backtracking.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive backtracking function explores up to 4 directions for each letter in the word.
• How many times: For each cell in the grid (rows * cols), it may explore up to 4 choices for each character in the word (word length).

How Execution Grows With Input

As the grid size and word length grow, the number of paths to check grows very fast.

Input Size (n = rows * cols)	Word Length (m)	Approx. Operations
10	3	About 10 * 4^3 = 640
100	5	About 100 * 4^5 = 10,2400
1000	6	About 1000 * 4^6 = 4,096,000

Pattern observation: The operations grow exponentially with the word length and linearly with the grid size.

Final Time Complexity

Time Complexity: O(N * 4^M)

This means the time grows linearly with the number of cells in the grid and exponentially with the length of the word.

Common Mistake

[X] Wrong: "The search only takes time proportional to the grid size because we just check each cell once."

[OK] Correct: Because the search explores many paths recursively for each letter, it can revisit cells in different paths, causing exponential growth with word length.

Interview Connect

Understanding this complexity helps you explain how backtracking explores many possibilities and why pruning or constraints matter in real problems.

Self-Check

"What if we limited the search to only horizontal and vertical directions instead of all four directions? How would the time complexity change?"

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