Coding interview problems › Backtracking

🧩 Backtracking Medium

Word Search

Word Search explained: DFS with backtracking over a letter grid, marking and unmarking visited cells, tested Python, complexity, pitfalls and a live visual.

Also searched as: word search in a grid DFS · word search backtracking · find a word in a 2D board of letters

🧩

Try it live Free

Backtracking: Subsets, Permutations & Pruning

In the Backtracking lab, watch choose, explore, un-choose grow and shrink the recursion tree; in Word Search the "choose" is marking a grid cell and the "un-choose" is restoring it.

Also useful: Number of Islands & Grid BFS

Open the playground →

The problem

Given a 2D grid of letters and a word, decide whether the word can be traced through the grid by moving between horizontally or vertically adjacent cells, using each cell at most once in the path.

Inputboard = ["ABCE", "SFCS", "ADEE"], word = "ABCCED"
OutputTrue
Inputsame board, word = "ABCB"
OutputFalse

The B would have to be reused.

The key insight

Start a depth-first search from every cell that matches the first letter. From a cell matching word[k], try the four neighbours for word[k+1]. Mark the current cell as in use while exploring and unmark it when you back out, so other paths can still use it.

Brute force first: Enumerating every path in the grid is exponential; backtracking only follows paths whose letters match the word so far.

Step-by-step approach

  1. Loop over every cell and call dfs(r, c, 0).
  2. In dfs, fail if out of bounds or board[r][c] != word[k].
  3. If k is the last index, return True.
  4. Temporarily overwrite the cell with a marker such as #, then recurse into the four neighbours with k + 1.
  5. Restore the original letter before returning (the un-choose step).

Python solution

PYTHON 3tested
def exist(board, word):
    if not word:
        return True
    rows, cols = len(board), len(board[0]) if board else 0
    grid = [list(r) for r in board]          # mutable copy

    def dfs(r, c, k):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != word[k]:
            return False
        if k == len(word) - 1:
            return True
        saved, grid[r][c] = grid[r][c], "#"    # mark in use
        found = (dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1) or
                 dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1))
        grid[r][c] = saved                     # un-mark
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Complexity

TimeO(m · n · 3^L)
SpaceO(L)

Each of the m × n start cells can launch a search of depth L (word length), and after the first step each cell has at most 3 unvisited neighbours.

Common mistakes

Frequently asked questions

What is the time and space complexity of Word Search?

O(m × n × 3^L) time in the worst case, where L is the word length, and O(L) space for the recursion stack (the marking is done in the grid itself).

How can I speed up Word Search?

Count letters first: if the board lacks enough of some letter, return False immediately. Also, if the last letter of the word is rarer on the board than the first, search for the reversed word.

How do I search for many words at once?

That is Word Search II. Put all words in a trie and run one DFS from each cell that walks the trie alongside the grid, so shared prefixes are explored once.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Backtracking Backtracking: Subsets, Permutations & Pruning lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.