79. Word Search — DSA Atlas

MediumBacktrackingDFS backtracking on a 2D boardGrid path search with in-place visited marking

Word Search

Given an m x n grid of characters board and a string word, return true if word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same cell may not be used more than once within a single word path.

Open official problem prompt ↗

In plain English

Decide whether the word can be traced as a self-avoiding path through orthogonally adjacent grid cells.

Picture it like this

Like a word-search puzzle: put your finger on a matching letter and see if you can walk to neighboring letters to spell the word without crossing your own trail.

Example

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Why: The path A(0,0) -> B(0,1) -> C(0,2) -> C(1,2) -> E(2,2) -> D(2,1) walks adjacent cells spelling ABCCED without reusing a cell.

Constraints

m == board.lengthn == board[i].length1 <= m, n <= 61 <= word.length <= 15board and word consist of only lowercase and uppercase English letters

Pattern lesson

See the pattern, then code

Grid path search with in-place visited marking

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Try each cell as the first letter; from a matching cell, recurse into its four neighbors for the next letter. Temporarily overwrite the visited cell with a sentinel so the current path cannot step on it, then restore it on the way back so other start paths remain valid.

New words, made simpleKnow these before the algorithm

Adjacent cells: The up/down/left/right neighbors of a cell (no diagonals).
In-place visited marker: Temporarily overwriting a cell with a sentinel like '#' to forbid reuse, restored after recursion.
Backtrack restore: Putting the original letter back so paths starting elsewhere can still use that cell.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

DFS with a separate visited set

Works fine and is very readable, but allocates a set and hashes tuples each step.

Keep a set of (r,c) coordinates added on entry and removed on exit.

Time O(m * n * 4^L)Space O(L) plus set overhead

Best choiceDFS with in-place sentinel

Same complexity with no auxiliary structure; only the recursion stack, and it is the classic concise solution.

Overwrite the current cell with '#' during recursion, restore it afterward, exploring all four directions.

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

The rule we keep true

Invariant

Every cell on the current recursion path is marked '#', so the in-progress path is self-avoiding; on return, the cell is restored to its original letter.

Why this is correct

Reasoning

The base case k == len(word) fires only after L consecutive letters matched along adjacent cells, which is exactly the definition of the word existing. Marking blocks the current path from reusing a cell; restoring guarantees independence between different start attempts, so no valid path is missed and no invalid (self-crossing) path is accepted.

The algorithm in three movesSay these aloud before coding

1If the whole word is matched (k == len(word)) return True

(0,0)=A matches word[0]

2Reject out-of-bounds cells and cells not equal to word[k]

(0,1)=B matches word[1]

3Mark the cell visited, recurse into all four neighbors for word[k+1], then restore the cell and return whether any branch succeeded

... (2,1)=D matches word[5] -> True

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read(0,0)='A'

2 · Askboard[0][0] == word[0]?

3 · Update statek=0

4 · ResultMatch; mark '#', recurse k=1

Key takeaway

The matched path snakes across the board spelling ABCCED, one cell per letter.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-6Success base case
If k reached the word length, every letter matched along a valid path, so return True.
2
Lines 7-8Bounds and mismatch guard
Reject cells outside the grid or whose letter does not equal the needed word[k].
3
Lines 9-14Mark, explore four ways, restore
Overwrite with '#', try all neighbors for the next letter with short-circuit or, then put the letter back and report success.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single-character word matching one cell
Word longer than the number of cells -> must return false
Repeated letters like the two C's, which the no-reuse rule still permits since they are different cells

Common beginner mistakes

Forgetting to restore board[r][c], which corrupts later start attempts
Checking bounds after indexing board[r][c] (index error) instead of before
Marking visited but not unmarking, turning a reusable cell permanently blocked

Check your understanding

Why must we restore the cell's letter after exploring its neighbors instead of leaving it marked?

PyPython 3 · solution.py

Optimal

1class Solution:2    def exist(self, board: list[list[str]], word: str) -> bool:3        rows, cols = len(board), len(board[0])45        def dfs(r: int, c: int, k: int) -> bool:6            if k == len(word):7                return True8            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[k]:9                return False10            tmp = board[r][c]11            board[r][c] = '#'12            found = (dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1) or13                     dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1))14            board[r][c] = tmp15            return found1617        for r in range(rows):18            for c in range(cols):19                if dfs(r, c, 0):20                    return True21        return False

Time complexityO(m * n * 4^L) where L = len(word)Optimized

Space complexityO(L)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MicrosoftAmazonBloombergMeta

Word Search

Word Search

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking