Word Search — DFS with Backtracking on a Grid (LC 79)

Problem Statement#

LeetCode 79 — Word Search (Medium)

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.

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.

Example:

Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]], word = "ABCCED"
Output: true
 
Input: board = [...same...], word = "SEE"
Output: true
 
Input: board = [...same...], word = "ABCB"
Output: false
Explanation: B at (0,1) cannot be reused for the trailing B.

Why This Problem Matters#

Word Search is the gold-standard DFS-with-backtracking interview problem on a grid. It is asked at every FAANG company at least once a year because it tests three skills simultaneously: DFS state management, backtracking with state restoration, and pruning to control the exponential blow-up.

Once you can write Word Search cleanly without bugs, you can write LC 212 (Word Search II), LC 39 (Combination Sum), LC 47 (Permutations), and dozens of other backtracking problems with minor variations. Top interviewers use it as a litmus test: candidates who handle the visited-cell restoration correctly without scaffolding hints typically pass; those who default to a global visited set without restoring it usually fail.

The Core Insight#

The search is a recursive walk through the grid with two terminating conditions:

• Success. We have matched all characters of word (index reached len(word)). Return true.
• Failure. Out of bounds, current cell does not match the next character, or cell is already on the current path.

The mark-and-restore pattern is what makes this DFS backtracking:

1. Before recursing into neighbors, set board[r][c] to a sentinel (e.g., '#') so the path-uniqueness invariant holds.
2. After all four recursive calls return, restore board[r][c] to its original character so other DFS branches can use it.

The outer loop tries every cell in the grid as a potential starting point and short-circuits the moment any DFS returns true.

Why backtracking, not a global visited set? Both work, but the in-place sentinel approach has zero extra memory and naturally restores when the recursion unwinds — fewer moving parts means fewer bugs.

Worst-case complexity. O(m times n times 4^L), where L is the length of word. The 4^L factor comes from each step having up to 4 choices. Pruning by character mismatch trims this dramatically in practice.

Visual Dry Run#

Board:

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

Word: "ABCCED".

The marked cells through this path: (0,0), (0,1), (0,2), (1,2), (2,2), (2,1). All restored on the way back up if the search continued — but here we short-circuit because of the success.

Solution (Optimal)#

Python#

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        R, C = len(board), len(board[0])
 
        def dfs(r: int, c: int, i: int) -> bool:
            if i == len(word):
                return True                      # matched all characters
            if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[i]:
                return False
 
            saved = board[r][c]                  # remember the original char
            board[r][c] = '#'                    # mark cell as on-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] = saved                  # restore (backtrack!)
            return found
 
        for r in range(R):
            for c in range(C):
                if dfs(r, c, 0):
                    return True
        return False

JavaScript#

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    const R = board.length, C = board[0].length;
 
    function dfs(r, c, i) {
        if (i === word.length) return true;             // word fully matched
        if (r < 0 || r >= R || c < 0 || c >= C) return false;
        if (board[r][c] !== word[i]) return false;
 
        const saved = board[r][c];                      // save original
        board[r][c] = '#';                              // mark as on-path
 
        const found = dfs(r + 1, c, i + 1)
                   || dfs(r - 1, c, i + 1)
                   || dfs(r, c + 1, i + 1)
                   || dfs(r, c - 1, i + 1);
 
        board[r][c] = saved;                            // backtrack: restore
        return found;
    }
 
    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
};

Time Complexity: O(m times n times 4^L) where L is word.length. Space Complexity: O(L) recursion stack.

Common Mistakes#

1. Forgetting to restore. Setting cell to '#' and never restoring it means subsequent starting points cannot reuse the cell — leading to false negatives.
2. Using a global visited set without clearing it. Visited state persists across DFS branches, causing false negatives. Either reset it or use the in-place sentinel.
3. Checking i == len(word) after the bounds/char checks. If you reorder, you can miss a successful end-of-word at an out-of-bounds neighbor.
4. Using i > len(word) instead of ==. A subtle off-by-one that fails silently.
5. Hard-coding 4 separate if blocks instead of an or. Verbose and easy to miss a branch; the or short-circuits naturally.

Interview Tips#

• Lead with the template. "DFS with mark-and-restore — also known as backtracking — is the standard approach."
• State complexity carefully. O(m times n times 4^L) is correct; using O(m times n) or O(4^L) alone underestimates.
• Mention pruning. "If the count of any character in word exceeds the count in the board, return false immediately." This is a one-line preflight that turns adversarial inputs into instant rejects.
• Trie optimization. Foreshadows LC 212 (Word Search II) — using a trie to search many words simultaneously.

Follow-up Questions#

1. What if you must search for many words at once? Use a trie (LC 212). Insert all words; DFS the grid while walking the trie.
2. What if the grid has weighted cells (e.g., max-cost path)? Use DP on subsets if the path length is bounded.
3. Allow diagonal moves? Add four diagonal direction tuples; everything else is identical.
4. What if the same cell can be reused? Drop the mark/restore; algorithm becomes simpler but exponential blow-up is worse.
5. How would you parallelize this? The outer loop over starting cells is embarrassingly parallel.

Key Takeaways#

• Word Search is DFS plus backtracking — every interview will probe this template.
• Mark cells with a sentinel before recursing; always restore on the way back up.
• Use or chaining of recursive calls so success short-circuits without redundant work.
• Time is O(m times n times 4^L); pruning by character frequency is a free optimization.
• Avoid global mutable state — local sentinel marking is more reliable.
• This template generalizes directly to LC 212, LC 980, and other "find a path that forms X" grid problems.