Generated by Codex with GPT-5

Difficulty: MEDIUM

Problem: Word Search

Problem gist

The problem gives a 2D grid of characters and a target word. The task is to decide whether the word can be formed by walking through adjacent grid cells. Each step may move up, down, left, or right, and the same cell cannot be used twice in the same word path.

This is a path-existence problem, not a shortest-path problem. The path only matters while trying one possible spelling of the word. If a path fails, the solution should undo that choice and try another route.

Solution idea

Use depth-first search with backtracking.

Start from every cell that matches the first character of the word. From that cell, recursively try to match the next character in each of the four directions. While a cell is part of the current path, temporarily mark it as visited so it cannot be reused. If the branch fails, restore the cell before trying the next branch.

Two small checks make the search much more practical:

• If the word is longer than the number of cells, it cannot fit.
• If the board does not contain enough copies of any required letter, the word cannot exist.

A useful extra optimization is to search the word from the rarer end. If the last character appears fewer times on the board than the first character, reverse the word before searching. This does not change the problem because valid paths can be read in either direction, but it usually reduces the number of starting points.

How to derive it

The key constraint is “do not reuse a cell.” That immediately rules out a simple greedy scan, because choosing a locally valid next cell can block the only valid continuation later. The algorithm needs a way to try a choice, explore its consequences, and then undo it.

That is exactly backtracking. Each recursive call represents one position in the word. The state is the current board cell and the index of the character being matched. A branch is valid only if the current cell has the needed character and has not already been used in this path.

Once the search reaches the last character, the whole word has been matched. If every possible starting cell and branch fails, there is no valid path.

Python solution

from collections import Counter
from typing import Counter as CounterType, List, Tuple


class Solution:
    DIRECTIONS: Tuple[Tuple[int, int], ...] = (
        (1, 0),
        (-1, 0),
        (0, 1),
        (0, -1),
    )
    VISITED_MARKER = "\0"

    def exist(self, board: List[List[str]], word: str) -> bool:
        if not word:
            return True

        if not board or not board[0]:
            return False

        row_count = len(board)
        column_count = len(board[0])

        if len(word) > row_count * column_count:
            return False

        board_counts = self._count_board_letters(board)
        if not self._board_has_required_letters(board_counts, word):
            return False

        # Starting from the rarer end usually cuts down the number of roots.
        if board_counts[word[-1]] < board_counts[word[0]]:
            word = word[::-1]

        for row in range(row_count):
            for column in range(column_count):
                if self._search_from(board, word, row, column, 0):
                    return True

        return False

    def _search_from(
        self,
        board: List[List[str]],
        word: str,
        row: int,
        column: int,
        word_index: int,
    ) -> bool:
        if board[row][column] != word[word_index]:
            return False

        if word_index == len(word) - 1:
            return True

        original_character = board[row][column]
        board[row][column] = self.VISITED_MARKER

        next_word_index = word_index + 1
        for row_delta, column_delta in self.DIRECTIONS:
            next_row = row + row_delta
            next_column = column + column_delta

            if self._is_inside_board(board, next_row, next_column) and self._search_from(
                board,
                word,
                next_row,
                next_column,
                next_word_index,
            ):
                board[row][column] = original_character
                return True

        board[row][column] = original_character
        return False

    def _is_inside_board(
        self,
        board: List[List[str]],
        row: int,
        column: int,
    ) -> bool:
        return 0 <= row < len(board) and 0 <= column < len(board[0])

    def _count_board_letters(self, board: List[List[str]]) -> CounterType[str]:
        counts: CounterType[str] = Counter()
        for row in board:
            counts.update(row)
        return counts

    def _board_has_required_letters(
        self,
        board_counts: CounterType[str],
        word: str,
    ) -> bool:
        word_counts = Counter(word)
        return all(
            board_counts[character] >= required_count
            for character, required_count in word_counts.items()
        )

Let m be the number of rows, n be the number of columns, and L be the word length. The preprocessing takes O(mn + L) time. The backtracking search is O(mn * 3^(L - 1)) in the worst case: after the first step, each branch usually has at most three useful directions because it cannot immediately return to the previous cell. The extra space is O(L) for the recursion stack, plus small letter-count maps.

Interview follow-ups

How would the solution change if the interviewer asks for all valid paths?

The DFS shape stays the same, but it cannot return as soon as it finds one match. Instead, it records the current path as a list of coordinates, appends a copy of that path whenever the last character is reached, and then continues backtracking.

This works because backtracking already enumerates every valid non-reusing path. The main tradeoff is output size. There can be exponentially many valid paths, so the time becomes proportional to the full search tree plus the number of coordinates returned. Space also grows with the output, although the active recursion path is still only O(L).

How would this extend to searching many words at once?

Searching each word independently repeats a lot of work. The standard upgrade is to build a trie from all target words and run one board DFS that follows trie edges. Whenever the search reaches a trie node that marks a full word, that word is found.

The trie works because many words share prefixes. If the current board path spells a prefix that is not in the trie, the search can stop immediately. This is the core idea behind Word Search II. The tradeoff is extra memory for the trie, roughly proportional to the total number of characters across all words, but it can reduce repeated DFS work dramatically.

Can the algorithm avoid mutating the board?

Yes. Instead of writing a temporary marker into the board, the search can keep a visited set or a boolean matrix for the current path. Before visiting a neighbor, it checks whether that coordinate is already present.

That version may be clearer in systems where mutating inputs is risky. The tradeoff is more memory and more per-step overhead. In LeetCode’s Python environment, temporary in-place marking is common because it avoids allocating or hashing coordinates on every recursive branch, while still restoring the board before returning.

Why is this not solved with breadth-first search?

Breadth-first search is best when the goal is to find a shortest path or explore states by distance. This problem only asks whether one exact word path exists, and every path must respect the no-reuse constraint.

A BFS state would need to carry the current cell, the word index, and the full set of used cells for that path. That makes the state large and expensive to copy. DFS backtracking keeps only one active path at a time, so it expresses the constraint more naturally and uses less working memory.

What if diagonal moves are allowed?

The search logic remains the same. Only the direction list changes from four directions to eight directions by adding the diagonals.

The branching factor increases, so the worst-case search gets larger. With eight possible moves, after the first step each branch can have up to seven non-immediate-backtracking choices, making the rough worst case O(mn * 7^(L - 1)). The same frequency checks and visited-cell rule still apply.