Word Search — LC 79 DFS + Backtracking on Grid

Problem Statement#

Given a 2D board of characters and a word, return true if the word can be constructed from sequentially adjacent cells (up, down, left, right). The same cell cannot be reused.

Constraints:

• m == board.length, n == board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• Letters are lowercase and uppercase English

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

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

Why This Problem Matters#

LC 79 is one of the most common 2D grid interview questions at Amazon, Microsoft, and Bloomberg. It tests whether you can compose three patterns smoothly: depth-first search, backtracking, and bounds-checked grid traversal.

This is also the gateway to LC 212 (Word Search II) where a Trie supercharges multi-word matching. Mastering LC 79 first lets you focus on the Trie when LC 212 shows up. Recruiters often start with LC 79 and escalate based on how cleanly you handle the visited-cell marking.

The Core Insight#

DFS from every cell that matches word[0]. At each step, mark the cell visited (set it to a sentinel like "#"), recurse into the four neighbors with word[k+1], then restore the cell on the way back.

Mutating the board in place avoids an O(m*n) visited array — a small but appreciated optimization. The base cases are k == len(word) (success) and out-of-bounds or mismatch (failure).

Visual Dry Run#

For board [["A","B"],["C","D"]], word "ABDC":

Solution (Optimal)#

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
 
        def dfs(r: int, c: int, k: int) -> bool:
            if k == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[k]:
                return False
            tmp = board[r][c]
            board[r][c] = "#"
            found = (dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1)
                     or dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1))
            board[r][c] = tmp
            return found
 
        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True
        return False

var exist = function(board, word) {
    const rows = board.length, cols = board[0].length;
 
    const dfs = (r, c, k) => {
        if (k === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[k]) return false;
        const tmp = board[r][c];
        board[r][c] = "#";
        const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1)
                   || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
        board[r][c] = tmp;
        return found;
    };
 
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
};

Time: O(m * n * 4^L) where L is word length. Space: O(L) recursion depth.

Common Mistakes#

• Using a separate visited set when mutating in place is simpler.
• Forgetting to restore the cell after recursion — kills future searches.
• Checking bounds after indexing into the board (causes index errors).
• Returning False instead of True on k == len(word).
• Starting DFS only from (0,0) instead of every matching cell.

Interview Tips#

• Use "#" as a sentinel; it cannot match any uppercase letter.
• Discuss pruning: if frequency count of any char in word exceeds count in board, return false early.
• Note that this is depth-first, not BFS — order matters because we backtrack.
• Mention Trie for LC 212 follow-up to show breadth.

Follow-up Questions#

• LC 212 Word Search II — multiple words, swap to a Trie.
• What if diagonal moves are allowed? Eight directions instead of four.
• Find all unique paths matching the word — collect rather than short-circuit.
• Lowercase vs uppercase — clarify case sensitivity.
• Very long words — recursion depth might overflow; switch to iterative.

Key Takeaways#

• DFS plus backtracking is the canonical pattern for 2D path problems.
• Mark visited in place, restore on return — no extra space needed.
• Start DFS from every cell that matches word[0].
• Bounds-check before indexing to avoid runtime errors.
• Time is O(mn4^L); space is O(L) recursion depth.
• Mismatch char count in board vs word is a fast prune.
• The pattern extends naturally to Word Search II via Trie.