Word Search

Difficulty: Medium Source: NeetCode

Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1: Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true

Example 2: Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true

Example 3: Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false

Constraints:

m == board.length, n == board[i].length

1 <= m, n <= 6

1 <= word.length <= 15

board and word consist of only lowercase and uppercase English letters.

Prerequisites

Before attempting this problem, you should be comfortable with:

DFS on a grid — traversing cells by exploring neighbors recursively
Backtracking — marking cells as visited, recursing, then unmarking to restore state
2D array indexing — handling row/col bounds carefully

Try starting the word search from every cell in the grid. From each starting cell, do a depth-first search that follows adjacent cells matching successive characters of word. Mark cells as visited during a path and unmark them when backtracking so other starting points or paths can use them. Return true as soon as a valid path is found.

Algorithm

For each cell (r, c) in the grid, call dfs(r, c, 0) where 0 is the current index in word.
In dfs(r, c, index):
- If index == len(word): return True (all characters matched).
- If out of bounds, already visited, or board[r][c] != word[index]: return False.
- Mark board[r][c] as visited (temporarily replace with #).
- Recurse in all 4 directions with index + 1.
- Unmark (restore the original character).
- Return whether any direction succeeded.

Solution

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, index):
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[index]:
            return False
        # mark as visited
        temp = board[r][c]
        board[r][c] = '#'
        # explore all 4 directions
        found = (dfs(r + 1, c, index + 1) or
                 dfs(r - 1, c, index + 1) or
                 dfs(r, c + 1, index + 1) or
                 dfs(r, c - 1, index + 1))
        # backtrack: restore cell
        board[r][c] = temp
        return found

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


board1 = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
print(exist(board1, "ABCCED"))  # True
print(exist(board1, "SEE"))     # True
print(exist(board1, "ABCB"))    # False

board2 = [["a"]]
print(exist(board2, "a"))       # True

Complexity

Time: O(m * n * 4^L) — for each of the m*n starting cells, DFS explores up to 4 directions at each of L steps
Space: O(L) — recursion depth equals word length L

Common Pitfalls

Not restoring the cell after backtracking. If you forget board[r][c] = temp, cells remain marked as # from a failed path and block other search paths. This is the backtracking step — without it, you’ll get incorrect False results.

Checking bounds after accessing the cell. Always check r < 0 or r >= rows or c < 0 or c >= cols before accessing board[r][c], or you’ll get an index out of range error.

Using a separate visited set vs. modifying in place. A visited set works too, but modifying the board in place (temporarily writing #) is slightly faster because it avoids set lookups. Just make sure to restore the original character.

Short-circuiting with or. The expression dfs(...) or dfs(...) or ... stops as soon as one direction returns True. This is efficient — once you find a valid path you stop exploring. Make sure this short-circuit doesn’t skip the restore step, which is why the restore happens after the found = ... line, not inside the or chain.

Note Book