Word Search in Grid Using Backtracking in DSA Javascript

Mental Model

We try to find the word by exploring each letter step-by-step in the grid, going back if a path doesn't work.

Analogy: Imagine walking through a maze where each step must match the next letter of a secret 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

Start searching from any cell that matches the first letter.

Dry Run Walkthrough

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

Goal: Find if the word 'ABCCED' exists in the grid by moving horizontally or vertically to adjacent letters.

Step 1: Start at cell (0,0) with letter 'A' matching first letter of word

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
↑ at (0,0) matching 'A'

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

Step 2: Move right to (0,1) with letter 'B' matching second letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
Path: A -> B ↑ at (0,1)

Why: Next letter must be adjacent and match 'B'

Step 3: Move right to (0,2) with letter 'C' matching third letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
Path: A -> B -> C ↑ at (0,2)

Why: Continue matching letters in order

Step 4: Move down to (1,2) with letter 'C' matching fourth letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
Path: A -> B -> C -> C ↑ at (1,2)

Why: Next letter must be adjacent vertically or horizontally

Step 5: Move down to (2,2) with letter 'E' matching fifth letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
Path: A -> B -> C -> C -> E ↑ at (2,2)

Why: Keep following the word letters

Step 6: Move left to (2,1) with letter 'D' matching sixth letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
Path: A -> B -> C -> C -> E -> D ↑ at (2,1)

Why: Last letter matched, word found

Result:

Word found with path: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1)

Annotated Code

DSA Javascript

class WordSearch {
  constructor(board) {
    this.board = board;
    this.rows = board.length;
    this.cols = board[0].length;
  }

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

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

    if (
      r < 0 || c < 0 || r >= this.rows || c >= this.cols ||
      this.board[r][c] !== 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, word, index + 1) ||
                  this.backtrack(r - 1, c, word, index + 1) ||
                  this.backtrack(r, c + 1, word, index + 1) ||
                  this.backtrack(r, c - 1, word, index + 1);

    this.board[r][c] = temp; // restore after backtracking
    return found;
  }
}

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

if (index === word.length) return true; // all letters matched

Check if full word matched to stop recursion

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

Stop if out of grid or letter does not match

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

Mark current cell as visited to avoid reuse

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

Explore all four directions recursively to find next letter

this.board[r][c] = temp; // restore after backtracking

Restore cell after exploring paths to allow other searches

Output

true

Complexity Analysis

Time: O(N * 3^L) because we start from each cell (N = rows*cols) and explore up to 3 directions for each letter in the word (L is word length)

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

vs Alternative: Naive approach without backtracking would try all paths blindly, causing exponential blowup; backtracking prunes invalid paths early

Edge Cases

Empty grid

Returns false immediately as no letters to match

DSA Javascript

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

Word longer than total cells

Returns false since word cannot fit

DSA Javascript

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

Word with repeated letters requiring revisiting cells

Cells are marked visited to prevent reuse, so revisiting same cell in one path is avoided

DSA Javascript

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

When to Use This Pattern

When you need to find a path matching a sequence in a grid or matrix with constraints on movement, use backtracking to explore and undo choices.

Common Mistakes

Mistake: Not marking cells as visited, causing infinite loops or incorrect matches
Fix: Mark cells visited before recursive calls and restore after to avoid reuse in the same path

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

Summary

Finds if a word exists in a grid by exploring adjacent letters step-by-step.

Use when searching for sequences in grids with movement constraints.

The key is to try paths and backtrack when a path fails, marking visited cells to avoid reuse.

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