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.
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
OutputSuccess
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.