Word Search (LeetCode 79)

The problem

You get a grid of letters and a word. Return True if the word can be spelled by walking through cells that are next to each other up, down, left or right, using each cell at most once in that word. Otherwise return False.

Input:
A B C E
S F C S
A D E E
word = "ABCCED"

Output: True

Start at A (0,0), go right to B and C, down to C (1,2), down to E (2,2), then left to D (2,1).

How to think about it

Start with brute force. Enumerate every path of length L from every cell and compare it to the word. With four directions that’s up to R·C·4^L paths, and most of them disagree with the word on the very first or second letter.

The key insight: match as you walk, and stop the moment a letter is wrong. Do a DFS that carries i, the index of the next letter needed. From cell (r, c), if the letter there isn’t word[i], return False straight away. Otherwise go to the four neighbours looking for word[i+1]. Most branches die after one or two steps, which is what makes this fast in practice.

The cell-reuse rule needs choose and undo. A path may not use the same cell twice, so mark the current cell as visited (overwrite it with '#') before exploring neighbours. Then, crucially, restore it on the way out. A different path, starting from somewhere else, may legitimately need that cell. A flood fill like Number of Islands marks cells forever; backtracking marks them only for the current path.

Which pattern is this? Backtracking on a grid: DFS plus mark/unmark. The tell is “find a path in a grid that spells / satisfies something, without revisiting cells”.

Approach

1. For every cell, call dfs(r, c, 0). Return True if any call succeeds.
2. dfs(r, c, i): if i == len(word), all letters matched, so return True.
3. If (r, c) is off the grid or board[r][c] != word[i], return False.
4. Save the letter, set the cell to '#', and try the four neighbours with i + 1.
5. Put the letter back, then return whether any neighbour succeeded.

Solution

def exist(board, word):
    R, C = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word): return True                       # every letter matched
        if r < 0 or c < 0 or r >= R or c >= C or board[r][c] != word[i]: return False
        tmp = board[r][c]; board[r][c] = '#'                  # choose: mark used on this path
        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))
        board[r][c] = tmp                                     # undo: free it for other paths
        return found
    for r in range(R):
        for c in range(C):
            if dfs(r, c, 0): return True
    return False
# exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED") -> True

Dry run

On the example grid with word = "ABCCED", the successful chain of calls:

For "ABCB" the same start reaches C at (0,2), but the only B next to it is (0,1), which is marked '#'. Every branch fails, the marks are undone, and the answer is False.

Complexity

• Time: O(R·C·4^L) for word length L. Each of the R·C starts can branch four ways at each letter. After the first step it’s really at most three ways (you can’t go back), so O(R·C·3^L) is a tighter bound.
• Space: O(L) for the recursion depth. Marking in place avoids a separate visited set.

Edge cases and pitfalls

• Forgetting to restore the cell. Later starting points then find '#' where a real letter should be, and you return False for words that exist.
• Reusing a cell. Without marking, "ABA" would match on a grid with just A B, by bouncing back.
• Single-cell grid: [["A"]] with "A" is True, with "AA" is False.
• Word longer than R·C can never fit. A quick length check, and a letter-count check against the grid, are cheap early exits.

Related problems

• Word Search II (LeetCode 212): many words at once, using a trie to share prefixes.
• Number of Islands (LeetCode 200): grid DFS where marks are permanent, not undone.
• N-Queens (LeetCode 51 / 52): another place-and-remove backtracking on a board.