Word Search Problem - Interactive Learning Guide

Problem Statement

Challenge

Given a 2D board and a string word, return True if the word can be formed by adjacent cells (up/down/left/right), without reusing any cell in the same path.

Example 1

Input / Output

board = [["A","B","C","D"],
         ["S","A","A","T"],
         ["A","C","A","E"]]
word = "CAT"
Output: True

Example 2

Input / Output

board = [["A","B","C","D"],
         ["S","A","A","T"],
         ["A","C","A","E"]]
word = "BAT"
Output: False

Key Insight: Start DFS from every cell. On match, mark current cell used, explore 4 directions for next index, then unmark on return.

O(m·4ⁿ)

Time Complexity

O(n)

Recursion Stack

n

Max Depth = len(word)

Core Concepts

Backtracking DFS Pattern

def dfs(r, c, i):
    if i == len(word):
        return True
    if invalid_state:
        return False

    mark(r, c)
    found = dfs(r+1,c,i+1) or dfs(r-1,c,i+1) or dfs(r,c+1,i+1) or dfs(r,c-1,i+1)
    unmark(r, c)
    return found

Always restore the cell after exploring neighbors. Failing to unmark causes false negatives later.

Decision State

(r, c): current board coordinates
i: index in word to match
path: currently used cells in this branch

Trace Example

state=(0,2,0)  need='C'  action=mark
state=(1,2,1)  need='A'  action=mark
state=(1,3,2)  need='T'  action=mark
state=(1,3,3)  action=success

When to Use This Pattern

1

Grid Path Existence

Need to confirm if any path forms a target string/pattern.

2

Local Moves

Movement is constrained to neighbors (4 or 8 directions).

3

No Reuse in One Path

Visited-state tracking is required for each recursion branch.

Step-by-Step Walkthrough

1

Initialize Dimensions

ROWS, COLS = len(board), len(board[0])

2

Base Case

if i == len(word):
    return True

3

Guard Invalid State

if r < 0 or c < 0 or r >= ROWS or c >= COLS:
    return False
if board[r][c] != word[i] or board[r][c] == '#':
    return False

4

Mark, Explore, Unmark

temp = board[r][c]
board[r][c] = '#'
res = dfs(r+1,c,i+1) or dfs(r-1,c,i+1) or dfs(r,c+1,i+1) or dfs(r,c-1,i+1)
board[r][c] = temp

5

Try Every Start Cell

for r in range(ROWS):
    for c in range(COLS):
        if dfs(r, c, 0):
            return True
return False

Complete Solution (Python)

python

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])

        def dfs(r, c, i):
            if i == len(word):
                return True
            if r < 0 or c < 0 or r >= ROWS or c >= COLS:
                return False
            if board[r][c] != word[i] or board[r][c] == '#':
                return False

            temp = board[r][c]
            board[r][c] = '#'
            res = (dfs(r + 1, c, i + 1) or
                   dfs(r - 1, c, i + 1) or
                   dfs(r, c + 1, i + 1) or
                   dfs(r, c - 1, i + 1))
            board[r][c] = temp
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

Interactive Visualizer

Word-

Current Index i-

Current Cell (r,c)-

Action-

Path[]

Knowledge Check

1. What is the worst-case time complexity?

A. O(m * n)

B. O(m * 2^n)

C. O(m * 4^n)

D. O(4^m)

Correct is C. We try m start cells, and each recursive level can branch to 4 neighbors.

2. Which invariant must hold for each DFS path?

A. Diagonal move happens at least once

B. No cell is reused in the same path

C. Start at (0,0)

D. Always go right first

Correct is B. Reusing a cell in one path violates the problem constraints.

3. For word length 1, when do we return true?

A. Board is square

B. First row contains the letter

C. Any cell matches word[0]

D. At least two matching cells exist

Correct is C. A single-character word needs one matching board cell.

4. What happens if we do not restore the board cell after recursion?

A. Algorithm turns iterative

B. Later paths read a mutated board and fail incorrectly

C. Only space complexity changes

D. Nothing changes

Correct is B. Mutation must be local to one path, then undone.

Code Playground

Output will appear here...

Alternative Approaches

1) Visited Matrix

Use visited[r][c] instead of mutating board cells.

visited = [[False] * COLS for _ in range(ROWS)]
# mark visited[r][c] = True before recursion
# reset to False after recursion

Time: O(m * 4^n) Space: O(ROWS*COLS + n)

2) Path Set

Track used cells in a set: path.add((r,c)) and remove on backtrack.

if (r, c) in path:
    return False
path.add((r, c))
# recurse
path.remove((r, c))

Time: O(m * 4^n) Space: O(n)

Common Mistakes

Forgetting to restore board[r][c] after recursion.
Checking character before bounds, causing invalid reads.
Not blocking cell reuse in the same path.
Starting DFS from only one cell instead of all cells.

Flashcards

Front: What is the base case in Word Search DFS?

Back: Return true when i == len(word). That means all characters were matched in order.

Front: Why O(m * 4^n)?

Back: There are m starting cells and up to 4 recursive branches for each of n character positions.

Front: Core intuition?

Back: Match -> mark cell used -> explore 4 neighbors -> unmark -> continue search.

Quick Reference

Template

def exist(board, word):
    ROWS, COLS = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or c < 0 or r >= ROWS or c >= COLS:
            return False
        if board[r][c] != word[i] or board[r][c] == '#':
            return False
        temp = board[r][c]
        board[r][c] = '#'
        ok = dfs(r+1,c,i+1) or dfs(r-1,c,i+1) or dfs(r,c+1,i+1) or dfs(r,c-1,i+1)
        board[r][c] = temp
        return ok

Mnemonic: Match -> Mark -> Explore 4 -> Unmark -> Repeat

Next Steps

Next Challenges

LeetCode 200 Number of Islands
LeetCode 130 Surrounded Regions
LeetCode 212 Word Search II
LeetCode 980 Unique Paths III

Study Schedule

Review this pattern after 1 day, 3 days, 7 days, and 14 days. Re-implement all three visited-state variants each review.