LeetCode #79 Medium

Word Search

Given a grid of characters and a word, decide whether the word can be spelled by walking through horizontally or vertically adjacent cells without reusing a cell.

backtrackingmatrixdfsarray

Open on LeetCode ↗

02

Intuition

💡

You will mark a cell visited so the path cannot walk back onto itself, and then you will forget to un-mark it when the path fails. That one missing line is what this problem exists to teach. Picture searching for SEE and starting at the wrong S: the walk marks four cells, dead-ends, and returns false — but those four cells are still flagged. When the correct anchor starts its search and needs one of them, the grid lies and says it is occupied, so a word that is genuinely on the board reports false. A failed attempt has poisoned the board for everyone after it. The fix is to restore the cell as the recursion unwinds: mark, recurse over the four neighbours, un-mark. That restore IS the backtracking; the DFS is just how you get around. The invariant is that a cell is marked used exactly while it sits on the path currently being explored, so the board is bit-for-bit identical every time control returns to a caller — which is the only reason each new anchor gets a fair search.

03

Approach

1

Try every cell as an anchor

Any cell holding the word's first letter could start a valid path, so scan the whole grid and launch a DFS from each match. Return true on the first success — this is an existence question, not a counting one, so there is nothing to gain from continuing once a path is found.

2

DFS with a matching index

The search carries the index of the letter it currently needs. Reject immediately if the position is off the grid, already on the path, or holds the wrong character; succeed when the index reaches the last letter. Checking the character before recursing is what keeps this near-linear in practice — a mismatch kills the branch at depth one rather than after exploring it.

3

Mark, recurse, restore

Before exploring the neighbours, overwrite the cell with a sentinel such as '#' so the path cannot revisit it. After all four neighbours have been tried and failed, write the original character back. Using the grid itself as the visited set costs no extra space, but it makes the restore non-negotiable — skip it and you have not just lost information, you have corrupted the input.

04

Solution & live demo

python

▶1class Solution:
▶2    def exist(self, board: list[list[str]], word: str) -> bool:
▶3        R, C = len(board), len(board[0])
▶4        if len(word) > R * C:
▶5            return False
▶6 
▶7        def dfs(r: int, c: int, k: int) -> bool:
▶8            if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[k]:
▶9                return False
▶10            if k == len(word) - 1:
▶11                return True
▶12 
▶13            tmp = board[r][c]
▶14            board[r][c] = '#'
▶15            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
▶16                if dfs(r + dr, c + dc, k + 1):
▶17                    return True
▶18            board[r][c] = tmp
▶19            return False
▶20 
▶21        for r in range(R):
▶22            for c in range(C):
▶23                if board[r][c] == word[0]:
▶24                    if dfs(r, c, 0):
▶25                        return True
▶26        return False

05

Edge cases

Word longer than the number of cells

It cannot possibly fit; every path exhausts its options and the scan returns false. A length check up front short-circuits it in O(1).

Single-character word

The base case fires on the anchor itself before any neighbour is examined, so the answer is simply whether that character appears anywhere in the grid.

A path that must reuse a cell, e.g. ABCB on a board where the second B is the first one

The visited mark blocks the revisit, the branch dies, and the answer is correctly false — reuse is forbidden by the problem.

The word starts on a cell that dead-ends

The failed branch un-marks every cell it touched on the way out, so the next anchor searches a fully restored board. This is the exact scenario the restore protects.

06

Complexity

Time

O(R * C * 3^L)

Space

O(L)

L is the word length; each step has three onward directions rather than four because you never walk straight back into the cell you came from, which is already marked.