79. Word Search

Reformulated question¶

Given a 2D board of letters and a word, return whether you can trace the word by moving up, down, left, or right, using each cell at most once.

Example: board=[["A","B"],["C","D"]], word="ABD" -> True because path is (0,0)->(0,1)->(1,1)

Key trick¶

Use DFS backtracking from every cell.

Match one character at a time.
Mark the current cell as used during this path.
Restore it when backtracking.
Stop as soon as the full word is matched.

Trap¶

Common mistakes:

Not tracking visited cells per path, so the same cell gets reused.
Using a global visited set and forgetting to unmark on backtrack.
Building and comparing whole path strings repeatedly, which is slower and unnecessary.
Forgetting early return once a path succeeds.
Mutating the board and not restoring it.

Why is this question interesting?¶

It is a clean backtracking problem with just enough state to expose whether you understand:

DFS on grids
per-path state
pruning
in-place marking vs extra memory

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("board", "word", "expected"),
    [
        (
            [["A", "B", "C", "E"],
             ["S", "F", "C", "S"],
             ["A", "D", "E", "E"]],
            "ABCCED",
            True,
        ),
        (
            [["A", "B", "C", "E"],
             ["S", "F", "C", "S"],
             ["A", "D", "E", "E"]],
            "SEE",
            True,
        ),
        (
            [["A", "B", "C", "E"],
             ["S", "F", "C", "S"],
             ["A", "D", "E", "E"]],
            "ABCB",
            False,
        ),
        (
            [["A"]],
            "A",
            True,
        ),
        (
            [["A"]],
            "B",
            False,
        ),
        (
            [["A", "A"]],
            "AAA",
            False,
        ),
        (
            [["C", "A", "A"],
             ["A", "A", "A"],
             ["B", "C", "D"]],
            "AAB",
            True,
        ),
        (
            [["A", "B"],
             ["C", "D"]],
            "ABCD",
            False,
        ),
    ],
)
def test_exist(board, word, expected):
    assert Solution().exist(board, word) is expected

Solve the problem with idiomatic python¶

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

        def dfs(r: int, c: int, i: int) -> bool:
            # All characters matched.
            if i == len(word):
                return True

            # Out of bounds or current cell does not match next needed char.
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
                return False

            # Mark this cell as used for the current path.
            ch = board[r][c]
            board[r][c] = "#"

            # Try all 4 directions for the next character.
            found = (
                dfs(r - 1, c, i + 1)
                or dfs(r + 1, c, i + 1)
                or dfs(r, c - 1, i + 1)
                or dfs(r, c + 1, i + 1)
            )

            # Restore the cell for other paths.
            board[r][c] = ch
            return found

        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True

        return False

Time: \(O(mn \cdot 4^L)\) in the worst case, where \(L = len(word)\)
Space: \(O(L)\) recursion stack

Comment my solution¶

Your solution has the right overall idea, but it misses the key visited-state rule.

Problems:

It never marks cells as used, so the same cell can be revisited in one path.
path stores letters only, not positions, so it cannot prevent reuse.
"" .join(path) is recomputed many times, which is avoidable overhead.
Using found is not needed; DFS can just return True or False.
Checking if found before calling dfs in the outer loop does nothing useful.

A simpler shape is:

DFS takes (r, c, i) where i is the index in word
Return boolean directly
Mark/unmark the board cell during recursion

For example, this is the missing bug in spirit:

board = [["A", "B"]]
word = "ABA"

Your code can reuse the first "A" again, which is illegal.

## Solution
class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        path = []
        # I don't like using found like this but I don't see how to do
        # it differently here.
        found = False

        def dfs(r,c):
            nonlocal found
            if "".join(path) == word:
                found = True
                return
            # path is not a prefix
            if "".join(path) != word[:len(path)]:
                return
            for i, j in [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]:
                if i < 0 or i >= m or j < 0 or j >= n:
                    continue
                path.append(board[i][j])
                dfs(i,j)
                path.pop()
        for r in range(m):
            for c in range(n):
                path = [board[r][c]]
                if found:
                    return True
                else:
                    dfs(r,c)
        return False

Solution().exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED") # True
# The following one return True on LeetCode server, but on my machine
# it returns the correct answer False which is also what LeetCode test
# seems to expect.
Solution().exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCD") # False