Word Search

A grid DFS can match the right letters and still be wrong. The missing piece is path-local state: mark a cell when you enter it, explore from that choice, then restore it before trying another branch.

Read the contract as a path problem

The task is to return a Boolean:

• True if the target word can be constructed in the grid.
• False otherwise.

A valid construction starts at any cell and moves between horizontally or vertically adjacent cells. Diagonal contact does not count. A coordinate can appear at most once in one candidate path.

That last condition changes the problem completely. Ordinary grid traversal asks, “Which cells can I reach?” Word Search asks, “Can I build this exact sequence along one legal path without consuming a coordinate twice?”

The direct solution is:

1. Try every cell as a possible start.
2. From a matching cell, recursively try its four neighbors for the next character.
3. Mark the current cell as used while its descendants are being explored.
4. Undo that mark before the recursive call returns.

This creates a search tree. Each node is a partial path; each child is one adjacent-cell choice. Bounds, character mismatches, and reused coordinates cut off branches before they grow.

The search is a backtracking grid path: choose a cell, explore the consequences, and undo the choice when that branch cannot finish the word.

Identify the state ordinary DFS misses

A brute-force approach would enumerate paths of the required length. That is already enough to expose the core issue: enumerating a path requires remembering which coordinates that path has consumed.

The recursive state needs three pieces:

• row: the current row.
• col: the current column.
• index: the position in word that this cell must match.

It also needs path visitation state. You can represent that state in either of two ways:

• Mutate the grid temporarily, replacing a used character with a sentinel.
• Maintain a separate visited set or Boolean matrix.

For the Python implementation, I prefer in-place marking. It keeps the path lifecycle visible in the code and avoids allocating an additional m × n structure. The tradeoff is that the input grid is temporarily mutated, so every mutation must be restored.

The visited state is path-local, not global.

Suppose one branch uses (1, 2) and later fails. A sibling branch may legally use (1, 2) as part of a different path. A global “ever visited” set would confuse those two cases and reject valid solutions.

That distinction produces the central failure modes:

• Mark without restoring: later branches incorrectly inherit an old path's restrictions.
• Restore too early: descendants can revisit a coordinate that is still supposed to be unavailable.
• Do not track visitation: repeated letters can make the algorithm walk in a cycle and reuse the same cell.

A visited cells DFS solution is correct only when the visited state describes the current recursion path, not the entire search history.

Derive choose, explore, and undo

Define the recursive question precisely:

Can a path beginning at (row, col) match word[index:], given the cells already used by its ancestors?

That question determines the control flow.

Reject impossible states first

For a candidate cell, reject it when:

1. It is outside the grid.
2. It is already marked by the current path.
3. Its character does not equal word[index].

These checks are safe pruning. An out-of-bounds coordinate cannot become valid later. A wrong character cannot match the current word position. A used coordinate cannot be reused within this path.

After those checks, if index points to the final character, the word has been matched.

Choose, explore, undo

For a non-final character:

1. Save the cell's original character.
2. Mark the cell as used.
3. Recursively explore its four edge-sharing neighbors with index + 1.
4. Restore the original character.
5. Return whether any neighbor succeeded.

The restoration belongs after all descendant exploration. It also belongs on the success path if the function mutates the input grid. Otherwise, the function may return True with part of the board still marked.

Path invariant: During a recursive call, the marked cells are exactly the coordinates in the current path, and those cells match the corresponding prefix of the word. When the call returns, its own mark has been removed, so the caller's path state is unchanged.

That invariant is the algorithm. The recursion is only the mechanism that moves from one path state to the next.

A separate visited matrix expresses the same lifecycle:

visited[row][col] = True
# explore descendants
visited[row][col] = False

In-place marking uses the original character as the value to restore:

original = board[row][col]
board[row][col] = "#"
# explore descendants
board[row][col] = original

The representation changes. The obligation does not.

Prove soundness, completeness, and no reuse

An interview-quality explanation should establish more than “the examples pass.”

Soundness

If the algorithm returns True, then:

• The starting cell came from the outer scan.
• Every recursive move stayed within bounds.
• Every move used one of the four edge-sharing directions.
• Each visited character matched the corresponding character in word.
• The visited check prevented a coordinate from appearing twice in that path.

Therefore, the returned path is a legal construction of the word.

Completeness

Assume a valid path exists.

The outer nested loop eventually tries its first coordinate because it examines every cell. From that start, the recursive loop tries all four possible directions at each step. The valid next coordinate is therefore included as one of the branches.

The same argument applies at every later position in the path. A valid branch is rejected only by one of three conditions:

• The coordinate is out of bounds.
• The character is wrong.
• The coordinate was already used in the current path.

None of those conditions can hold for a valid next step. So the valid path remains available and is eventually found.

No reuse

When a recursive call marks (row, col), that coordinate remains unavailable to all descendants of the call. A descendant can see the sentinel and reject it.

Only after every descendant branch has finished does the call restore the original character. At that point, the coordinate becomes available to sibling branches and later starting positions.

This is why both operations matter:

• Marking enforces no reuse inside the current branch.
• Unmarking prevents one failed branch from poisoning other branches.

A missing undo is not a small cleanup bug. It changes the search space.

An early undo is equally dangerous. If you restore the cell before all descendants finish, a deeper call can step back onto it and create an illegal path.

Dry-run a failing branch and recovery

Use this grid:

A B C E
S F C S
A D E E

and search for ABCCED.

One successful path is:

(0, 0) A
(0, 1) B
(0, 2) C
(1, 2) C
(2, 2) E
(2, 1) D

The interesting part is not merely finding that path. It is watching the algorithm reject bad choices and recover.

The first few recursive calls look like this:

Step	Coordinate	Expected	Current path
1	(0, 0)	A	A
2	(0, 1)	B	A → B
3	(0, 2)	C	A → B → C

From (0, 2), the algorithm tries neighbors in the chosen direction order. Some branches fail immediately:

• (0, 3) contains E, but the next expected character is C.
• Moving upward is out of bounds.
• Returning to (0, 1) would find B, not C, and that coordinate is already in the path anyway.

Eventually it tries (1, 2), which contains the next C. That cell is marked while its descendants are explored.

From there, (1, 3) contains S, so it cannot satisfy the expected E. The search restores (1, 2) when that branch is exhausted and tries the next legal direction. It reaches (2, 2), then (2, 1) for the final D.

Repeated characters make this harder to reason about. In the example, both (0, 2) and (1, 2) contain C, so matching the letter is not enough. The algorithm must distinguish coordinates, not just values. A repeated character is a valid choice only when its coordinate is not already part of the current path.

When debugging, log two events:

enter(row, col, index, path)
restore(row, col, path)

If the path contains a coordinate twice, the visited check is wrong. If a later branch starts with cells from an earlier branch still marked, restoration is missing or occurs on only one return path.

Implement the Python solution

The code below uses one consistent index convention: index identifies the character matched by the current cell. The success check occurs after bounds, visitation, and character checks, when index == len(word) - 1.

from typing import List


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

        directions = (
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        )

        def backtrack(row: int, col: int, index: int) -> bool:
            # Reject coordinates that cannot participate in this path.
            if row < 0 or row >= rows or col < 0 or col >= cols:
                return False

            # The sentinel means this coordinate is already in the path.
            if board[row][col] == "#":
                return False

            # The current cell must match the current word position.
            if board[row][col] != word[index]:
                return False

            # This cell completes the word.
            if index == len(word) - 1:
                return True

            # Choose: consume this coordinate for the current path.
            original = board[row][col]
            board[row][col] = "#"

            # Explore: extend the path in each edge-sharing direction.
            found = False
            for row_delta, col_delta in directions:
                next_row = row + row_delta
                next_col = col + col_delta

                if backtrack(next_row, next_col, index + 1):
                    found = True
                    break

            # Undo: make this coordinate available to sibling branches.
            board[row][col] = original
            return found

        # Any cell may be the first character of the word.
        for row in range(rows):
            for col in range(cols):
                if backtrack(row, col, 0):
                    return True

        return False

The important mutation boundary is narrow and visible:

original = board[row][col]
board[row][col] = "#"
# recursive exploration
board[row][col] = original

The found variable is deliberate. It ensures restoration happens before returning success. A tempting shortcut is:

if backtrack(next_row, next_col, index + 1):
    return True

That shortcut is logically fine only if the current cell is restored first. Returning directly would leave the current cell marked in the caller's grid.

You can also write the implementation with a separate visited matrix when mutating input is undesirable:

visited[row][col] = True
# explore
visited[row][col] = False

The matrix adds memory, but it can make the original board easier to inspect. Choose based on the surrounding API contract. In an interview, explain the lifecycle either way.

Analyze complexity and useful pruning

Let:

• M = m × n, the number of cells.
• L = len(word), the target length.

The outer loop gives up to M starting cells. From each position, the straightforward interview bound is:

O(M · 4^L)

That bound treats every level as having up to four choices.

The grid gives a slightly tighter view. After the first move, the immediately previous coordinate is already used, so there are at most three forward choices. This gives:

O(M · 4 · 3^(L - 1))

under the standard model.

Both describe exponential worst-case search. The precise constant is less important than recognizing why the tree can become large: a board with many repeated letters can keep numerous branches alive until late in the word. A board that almost matches the target but fails near the end forces the algorithm to revisit many similar partial paths.

A successful path may terminate the search early, but that is an observed best-case behavior, not a better worst-case guarantee.

With in-place marking:

• Recursion depth is at most L.
• Auxiliary space is O(L), excluding the input grid.

With a separate visited matrix, auxiliary space becomes:

O(L + M)

The M term is for the matrix, and the L term is for recursion.

For a larger board, you can add a character-frequency precheck. If the grid does not contain enough copies of some character required by the word, return False before searching. This is safe because a path cannot create characters that are absent from the board. It is an optimization, not part of the core correctness argument, and it does not change the worst-case exponential class.

You can also choose which direction to search first, but direction ordering is a heuristic. It may find a valid path sooner on some inputs; it does not remove the hard cases.

Edge cases and interview failure modes

Use these cases to test the contract and the state lifecycle:

• A one-cell board with a matching one-character word.
• A one-cell board with a different character.
• A word longer than the number of cells. It must fail because coordinates cannot be reused.
• Repeated letters that tempt the search into a cycle.
• A valid path beginning in a corner.
• A valid path that runs along a boundary.
• A word whose letters appear in the grid but have no legal edge-adjacent arrangement.
• A diagonal-looking arrangement that must be rejected.
• A word that is absent even though its first character appears many times.

The common implementation mistakes are predictable:

1. Allowing diagonal moves.
   Use exactly four direction offsets, not eight.

2. Using a global visited set.
   Visitation belongs to the current path. Remove the mark during backtracking.

3. Forgetting to unmark on failure.
   Later branches and starting cells then see stale state.

4. Restoring too early.
   A descendant can reuse a coordinate that should remain blocked.

5. Mixing index conventions.
   Decide whether the helper receives the index of the current character or the next character. Do not combine index == len(word) with a helper that still reads word[index].

6. Returning before restoring.
   If the board is mutated, restore it on the successful path as well as the failed path.

7. Checking only character counts.
   Having enough copies of each letter is necessary but not sufficient. Adjacency and no-reuse constraints still determine the answer.

The operational sequence is short enough to memorize, but do not memorize it as a code template:

Validate the contract. Define the state. Check rejection conditions. Mark. Recurse. Undo. Prove the invariant. Analyze the search tree.

The transferable pattern

Word Search becomes recognizable when three signals appear together:

• You must assemble a sequence through local choices.
• Each choice constrains the next position.
• A partial attempt may fail, but its choices must become available again for another attempt.

That combination calls for reversible path state.

Before writing recursion, name four things:

1. Choice: Which adjacent cell can I take next?
2. Constraint: Is it in bounds, does it match, and has this path already used it?
3. Invariant: What exactly does the current recursive state guarantee?
4. Undo: Which mutation must be reversed before the caller tries a sibling branch?

Once those are explicit, the code is mostly bookkeeping. The real skill is seeing that the grid is not merely a matrix to traverse. It is a branching search space, and the current path is temporary state that must be built, tested, and dismantled without leaving debris behind.