Algorithm

Word Search

Backtracking Pattern

Word Search

Given an m x n grid of characters and a string word, return true if the word can be traced on the grid.

A trace is a path of sequentially adjacent cells — horizontally or vertically neighbouring, never diagonally — whose letters spell the word in order. No cell may be used more than once within the same trace.

Only a boolean is required; the path itself is not returned. The search may begin at any cell.

CONSTRAINTS
  • m == board.length, n == board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consist of English letters
  • Matching is case-sensitive: 'A' and 'a' are different characters
EXAMPLE 1
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
The path runs A(0,0), B(0,1), C(0,2), then down to C(1,2), down to E(2,2), and left to D(2,1). A trace may change direction freely — it is not required to keep going the same way.
EXAMPLE 2
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Starting at S(1,3), down to E(2,3), then left to E(2,2). Note there is another S at (1,0) which leads nowhere — the search must be willing to try every starting cell, not just the first letter match it finds.
EXAMPLE 3
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
A, B and C trace fine, but the final B would require returning to (0,1), which is already part of this path. The no-reuse rule is what makes this false — without it the answer would be true.
EXAMPLE 4
Input: board = [["a"]], word = "a"
Output: true
A single cell matching a single character succeeds with no movement at all. The base case must fire on a fully matched word before any neighbour is examined, or this input fails.
Can a cell be reused within the same word?
No. That restriction is the entire reason this needs backtracking rather than a plain search — cells must be marked while a path uses them and released when it backs out.
Are diagonal moves allowed?
No, only the four orthogonal directions. A variant permitting all eight is common, so it is worth confirming.
Is the matching case-sensitive?
Yes, 'A' and 'a' are distinct. The constraints say English letters rather than lowercase letters specifically, so do not assume a single case.
Do I need to return the path, or may I modify the board?
Only a boolean is needed. Modifying the board in place is the standard trick for marking visited cells, but every mark must be restored — leaving the board altered when the function returns is a side effect the caller will not expect.

Trace a word through the grid, stepping to up/down/left/right neighbours, never reusing a cell in the same path. Same template — but we want a yes/no answer, so the recursion returns True/False and stops at the first match. The shared state we change is the board itself: mark a cell while the path is on it, unmark it on the way out.

The backtracking template

Every problem in this section is the same loop — three beats: choose, explore, un-choose.

python
def backtrack(state):
    if done(state):
        save(state)              # record the finished answer
        return
    for choice in choices(state):    # what can I pick right now?
        if not ok(choice):
            continue                 # prune: skip bad picks early
        apply(choice)                # CHOOSE
        backtrack(next_state)        # EXPLORE
        undo(choice)                 # UN-CHOOSE: put it back

Only four slots change between problems: done, choices, ok (pruning), and how you finish (save every answer, or return True at the first one). Fill those and the problem is solved.

What changes here
- A choice = step to an adjacent cell matching the next letter.
- Choices = the 4 neighbours (up / down / left / right).
- Done = matched the whole word → return True (stop everything).
- Prune = off the board, wrong letter, or cell already used this path.
python
def exist(board, word):
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, i):
        if i == len(word):
            return True                       # whole word matched
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False                      # PRUNE: off-grid / wrong / used
        board[r][c] = '#'                     # CHOOSE: mark used
        found = (backtrack(r+1, c, i+1) or backtrack(r-1, c, i+1) or
                 backtrack(r, c+1, i+1) or backtrack(r, c-1, i+1))   # EXPLORE
        board[r][c] = word[i]                 # UN-CHOOSE: restore
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

Restore the cell even when found is True — the board belongs to the caller, so leave it clean. The '#' mark is what enforces "no reuse in this path": a neighbour already marked '#' fails the letter test.

Trace "ABCB": A → B → C, then the last B needs the B cell again, but it's '#' now → fails → the whole trace returns false.

Interactive Strategy Visualization

Word Search (DFS)

Searching: ABCCED
A
B
C
C
E
D
A
B
C
E
S
F
C
S
A
D
E
E
Goal: Find if the word 'ABCCED' exists in the grid. We can move Up, Down, Left, Right.
MINDSET

We explore the grid like a graph. Every cell is a node, and every adjacent cell is an edge. We only traverse an edge if the character matches the next one in our target word.

BACKTRACKING

We must mark cells as 'visited' during a path to avoid cycles, but we MUST unmark them (backtrack) so they can be reused in different branches.

O(M × N × 4ᴸ) Four Directions At Every Step
→
O(M × N × 3ᴸ) Never Revisiting The Cell Just Left
→
O(M × N × 3ᴸ) With First-Letter Filtering