Word Search in Grid Using Backtracking in DSA Python

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 searching for a hidden path in a maze where you try one direction, and if it leads nowhere, you return and try another path until you find the correct way.

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

Start at any cell matching first letter, move up/down/left/right to next letter, mark visited cells to avoid reuse.

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 without reusing cells.

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

Visited: (0,0)
Grid:
[A] B C E
S F C S
A D E E

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

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

Visited: (0,0), (0,1)
Grid:
[A][B] C E
S F C S
A D E E

Why: Next letter must be adjacent and match the word

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

Visited: (0,0), (0,1), (0,2)
Grid:
[A][B][C] E
S F C S
A D E E

Why: Continue matching letters in sequence

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

Visited: (0,0), (0,1), (0,2), (1,2)
Grid:
[A][B][C] E
S F [C] S
A D E E

Why: Next letter must be adjacent vertically or horizontally

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

Visited: (0,0), (0,1), (0,2), (1,2), (2,2)
Grid:
[A][B][C] E
S F [C] S
A D [E] E

Why: Continue following the word path

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

Visited: (0,0), (0,1), (0,2), (1,2), (2,2), (2,1)
Grid:
[A][B][C] E
S F [C] S
A [D] [E] E

Why: Last letter matched, word found

Result:

Visited cells form path: (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,1)
Word 'ABCCED' found in grid

Annotated Code

DSA Python

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        visited = [[False]*cols for _ in range(rows)]

        def backtrack(r, c, index):
            if index == len(word):
                return True
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return False
            if visited[r][c] or board[r][c] != word[index]:
                return False

            visited[r][c] = True
            # Explore neighbors: up, down, left, right
            if (backtrack(r+1, c, index+1) or
                backtrack(r-1, c, index+1) or
                backtrack(r, c+1, index+1) or
                backtrack(r, c-1, index+1)):
                return True
            visited[r][c] = False
            return False

        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0]:
                    if backtrack(i, j, 0):
                        return True
        return False

# Driver code
board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]
word = 'ABCCED'
sol = Solution()
print(sol.exist(board, word))

if index == len(word):

Check if all letters matched; success base case

if r < 0 or c < 0 or r >= rows or c >= cols:

Stop if out of grid bounds

if visited[r][c] or board[r][c] != word[index]:

Skip if cell already used or letter mismatch

visited[r][c] = True

Mark current cell as used

if (backtrack(r+1, c, index+1) or backtrack(r-1, c, index+1) or backtrack(r, c+1, index+1) or backtrack(r, c-1, index+1)):

Try all four directions to find next letter

visited[r][c] = False

Backtrack: unmark cell if path fails

for i in range(rows): for j in range(cols): if board[i][j] == word[0]: if backtrack(i, j, 0): return True

Start search from every cell matching first letter

Output

True

Complexity Analysis

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

Space: O(L) for recursion stack and visited tracking for word length L

vs Alternative: Naive brute force without backtracking would be exponential and inefficient; backtracking prunes invalid paths early

Edge Cases

Empty grid or empty word

Returns False immediately as no word can be found

DSA Python

if index == len(word):

Word longer than total cells

Returns False since word cannot fit

DSA Python

if index == len(word):

Word with repeated letters requiring careful visited marking

Backtracking ensures cells are not reused incorrectly

DSA Python

if visited[r][c] or board[r][c] != word[index]:

When to Use This Pattern

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

Common Mistakes

Mistake: Not marking cells as visited before recursive calls, causing reuse of same cell multiple times
Fix: Mark the cell as visited before recursive calls and unmark it after to avoid reuse

Mistake: Not checking boundary conditions before accessing grid cells
Fix: Always check if row and column indices are within grid bounds before accessing

Summary

Find if a word exists in a grid by moving stepwise in four directions without reusing cells.

Use when searching for sequences in grids with adjacency and no repetition constraints.

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

Practice

1. What is the main purpose of using backtracking in a word search grid problem?

easy

A. To count the number of words in the grid

B. To sort the grid alphabetically

C. To replace characters in the grid

D. To explore all possible paths to find the word

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 unrelated 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 D

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
• Ignoring the recursive exploration nature

2. Which of the following is the correct way to check if a position (row, col) is inside the grid boundaries in Python?

easy

A. if 0 <= row < len(grid) and 0 <= col < len(grid[0]):

B. if row > 0 and col > 0 and row < len(grid) and col < len(grid[0]):

C. if row <= len(grid) and col <= len(grid[0]):

D. if row >= 0 or col >= 0:

Solution

1. Step 1: Understand grid boundary conditions

   Valid indices must be greater or equal to 0 and less than the number of rows or columns.

2. Step 2: Analyze each option

   if 0 <= row < len(grid) and 0 <= col < len(grid[0]): correctly uses inclusive lower bound and exclusive upper bound checks. if row > 0 and col > 0 and row < len(grid) and col < len(grid[0]): excludes 0 index, which is invalid. if row <= len(grid) and col <= len(grid[0]): allows equal to length, which is out of range. if row >= 0 or col >= 0: uses 'or' which is incorrect logic.

3. Final Answer:

   if 0 <= row < len(grid) and 0 <= col < len(grid[0]): -> Option A

4. Quick Check:

   Boundary check = if 0 <= row < len(grid) and 0 <= col < len(grid[0]): [OK]

Hint: Use 0 <= index < length for valid grid positions [OK]

Common Mistakes:

• Using > 0 instead of >= 0 excludes first row/column
• Allowing index equal to length causes errors
• Using 'or' instead of 'and' in conditions

3. What will be the output of the following code snippet?

grid = [['A','B','C','E'],
        ['S','F','C','S'],
        ['A','D','E','E']]
word = "ABCCED"

# Function to check word existence
result = word_search(grid, word)
print(result)

# Assume word_search uses backtracking to find the word

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Understand the word and grid

   The word "ABCCED" can be found by moving right and down in the grid starting at grid[0][0].

2. Step 2: Confirm backtracking finds the word

   Backtracking explores neighbors and matches letters sequentially, so it returns True if the word exists.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Word found = True [OK]

Hint: Trace letters stepwise to confirm word presence [OK]

Common Mistakes:

• Assuming word is not found without tracing
• Confusing output with None or error
• Ignoring backtracking's path exploration

4. Identify the bug in this backtracking snippet for word search:

def backtrack(r, c, index):
    if index == len(word):
        return True
    if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != word[index]:
        return False
    temp = grid[r][c]
    grid[r][c] = '#'
    found = (backtrack(r+1, c, index+1) or
             backtrack(r-1, c, index+1) or
             backtrack(r, c+1, index+1) or
             backtrack(r, c-1, index+1))
    grid[r][c] = temp
    return found

medium

A. Using '#' as marker can conflict with grid letters

B. Missing base case for index == 0

C. No bug; code is correct

D. Modifying grid in place without restoring causes errors

Solution

1. Step 1: Analyze the backtracking logic

   The code marks visited cells with '#', explores neighbors recursively, and restores the cell after exploration.

2. Step 2: Check for bugs

   Restoring the cell after recursion prevents errors. Base case for index == len(word) is correct. '#' is a common marker and safe if not in original grid.

3. Final Answer:

   No bug; code is correct -> Option C

4. Quick Check:

   Code logic = Correct [OK]

Hint: Check if visited cells are restored after recursion [OK]

Common Mistakes:

• Forgetting to restore grid cell after recursion
• Adding unnecessary base cases
• Assuming marker conflicts without checking grid content

5. Given a 4x4 grid and a list of words, which approach best finds all words using backtracking efficiently? A) Run backtracking separately for each word on the entire grid. B) Sort words alphabetically and search in order. C) Search only the first letter of each word and stop. D) Build a Trie of words and backtrack once to find all words simultaneously.

hard

A. Run backtracking separately for each word on the entire grid.

B. Build a Trie of words and backtrack once to find all words simultaneously.

C. Search only the first letter of each word and stop.

D. Sort words alphabetically and search in order.

Solution

1. Step 1: Understand the problem of multiple words

   Running backtracking separately for each word is inefficient because it repeats searches.

2. Step 2: Use Trie to optimize search

   Building a Trie of all words allows a single backtracking pass to find all words by prefix matching, improving efficiency.

3. Step 3: Eliminate other options

   Searching only first letters or sorting words does not improve search efficiency significantly.

4. Final Answer:

   Build a Trie of words and backtrack once to find all words simultaneously. -> Option B

5. Quick Check:

   Trie + backtracking = Efficient multi-word search [OK]

Hint: Use Trie to find multiple words in one backtracking pass [OK]

Common Mistakes:

• Running backtracking repeatedly wastes time
• Ignoring prefix sharing among words
• Assuming sorting helps search efficiency