Word Search I and II — DFS Backtracking on a Grid with Trie Acceleration

Problem Statement#

LC 79 — Word Search. Given an m x n grid of characters and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically neighboring). The same letter cell may not be used more than once.

LC 212 — Word Search II. Given the same grid and an array of words, return all words that exist in the grid. Multiple words can be searched in a single pass.

Constraints: 1 <= m, n <= 12 (LC 79). For LC 212: 1 <= m, n <= 12, 1 <= words.length <= 30000, 1 <= words[i].length <= 10.

Examples:

Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]],
       word = "ABCCED"
Output: true                # path A(0,0)->B(0,1)->C(0,2)->C(1,2)->E(2,2)->D(2,1)
 
Input: board = [["o","a","a","n"],
                ["e","t","a","e"],
                ["i","h","k","r"],
                ["i","f","l","v"]],
       words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Why This Problem Matters#

Grid-DFS backtracking is one of the top three patterns FAANG interviewers reach for, alongside subsets and N-Queens. Word Search shows up in Amazon onsites at least monthly, Meta uses LC 212 specifically as a senior screen, and Google has a long history of asking the trie variant for backend SDE roles.

The skills tested are exactly the skills you need to build production-grade autocomplete (where a trie indexes a vocabulary), spell check, mobile keyboard prediction, and crossword puzzle generators. Boggle — the word game LC 212 is essentially modeling — was famously solved at Google with this exact algorithm during a hackathon, leading to several published research papers on grid-trie pruning.

The contrast between LC 79 (single word) and LC 212 (many words) also teaches the crucial optimization lesson: when you're searching for many patterns at once, index the patterns first. The naive multi-word search runs LC 79 once per word; the trie version runs ONE DFS that tracks all words simultaneously and prunes aggressively when no word in the dictionary continues with the current prefix.

The Core Insight#

Word Search is depth-first search where the implicit graph is the grid (each cell is a node, edges connect orthogonally adjacent cells) and the constraint is that the visited path spells a target string. At cell (r, c) matching word[i], the recursion explores the four neighbors looking for word[i + 1]. Marking (r, c) as visited (typically by writing a sentinel like # into the cell, then restoring) prevents revisiting on the current path.

For LC 79 the algorithm is:

1. For each cell that matches word[0], launch a DFS.
2. Inside DFS at (r, c) with index i: if i == len(word), return True. Else mark, try four neighbors with i + 1, unmark on return.
3. Return True as soon as any branch finds the word.

For LC 212 the trie acceleration is the difference between AC and TLE. Build a trie from all words, then run DFS once. Each DFS state carries a trie node; you only continue when the current cell's letter is a child of that node. When the trie node has is_word, record the word and (optimization) prune that leaf to avoid duplicate finds.

The visited-mark-in-place trick is critical: instead of allocating a visited 2D array, write a sentinel (like #) into board[r][c], recurse, then restore the original character. This saves O(m * n) memory and avoids allocation churn. It is the production-quality move interviewers expect at L5+.

Visual Dry Run#

LC 79 with word = "ABCCED" on the 3x4 board.

Search start cells with letter A: (0,0), (2,0)
  Start (0,0):
    i=0 'A' OK -> mark (0,0)='#'
      Try (1,0)='S' -> word[1]='B' no
      Try (-1,0) -> out of bounds
      Try (0,1)='B' OK -> mark (0,1)='#'
        Try (0,2)='C' OK -> mark (0,2)='#'
          Try (1,2)='C' OK -> mark (1,2)='#'
            Try (2,2)='E' OK -> mark (2,2)='#'
              Try (2,1)='D' OK -> mark (2,1)='#' -> i=6 == len(word) -> RETURN True

Each successful match propagates True up; backtrack restores marks if a branch fails. With the trie LC 212 version, every neighbor step also walks one node in the trie, instantly pruning paths whose prefix is not in the dictionary.

Solution (Optimal)#

Python — LC 79 single word DFS#

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
 
    def dfs(r: int, c: int, i: int) -> bool:
        # Base: matched all letters
        if i == len(word):
            return True
        # Bounds + match check
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or board[r][c] != word[i]):
            return False
        # Mark visited in place
        saved = board[r][c]
        board[r][c] = '#'
        # Explore four directions
        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))
        # Unchoose: restore for sibling branches
        board[r][c] = saved
        return found
 
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == word[0] and dfs(r, c, 0):
                return True
    return False

Python — LC 212 multi-word with trie#

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    # Build trie
    root: dict = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node['$'] = w  # store word at terminal node
 
    rows, cols = len(board), len(board[0])
    found: list[str] = []
 
    def dfs(r: int, c: int, node: dict) -> None:
        ch = board[r][c]
        if ch not in node:
            return  # prefix not in dictionary -> prune
        nxt = node[ch]
        if '$' in nxt:
            found.append(nxt.pop('$'))  # remove to avoid duplicate finds
 
        board[r][c] = '#'
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                dfs(nr, nc, nxt)
        board[r][c] = ch
 
        # Optional: prune empty branches from trie to speed up siblings
        if not nxt:
            node.pop(ch, None)
 
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return found

JavaScript — LC 79#

function exist(board, word) {
    const rows = board.length, cols = board[0].length;
 
    function dfs(r, c, i) {
        if (i === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols
                || board[r][c] !== word[i]) return false;
 
        const saved = board[r][c];
        board[r][c] = '#';
        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;
        return found;
    }
 
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (board[r][c] === word[0] && dfs(r, c, 0)) return true;
        }
    }
    return false;
}

Complexity#

W is the word count, L is the max word length. Trie acceleration is essentially independent of W on real workloads.

Common Mistakes#

1. Forgetting to unmark. Leaving board[r][c] = '#' after DFS returns prevents sibling branches from using the cell on a different path. Always restore.
2. Using a separate visited set or 2D array. Works correctly but doubles memory. The in-place sentinel trick is faster and uses O(1) extra space per cell.
3. Bounds check after array access. Writing if board[r][c] != word[i] before bounds checking causes IndexError. Always check 0 less-than-or-equal r less-than rows first.
4. Not pruning trie leaves. In LC 212, popping '$' after recording prevents the same word from being recorded twice when it appears in multiple grid paths.
5. Mutating the input string. Some candidates try word = word[1:] recursively, which copies the string each call — O(L^2) wasted work. Pass an integer index instead.
6. Returning the result instead of propagating early. LC 79 should short-circuit the moment any branch returns True. Forgetting or between recursive calls or using if all(...) returns wrong results.

Interview Tips#

• State the algorithm in one sentence. "DFS from each starting cell that matches the first letter, with in-place visited marking and four-direction recursion."
• Discuss complexity carefully. 4^L is the worst case branching; the actual explored subtree is usually much smaller because of early character mismatch.
• Suggest the trie variant unprompted for LC 212. It is the differentiator between mid and senior signal.
• Optimize order of starting cells. Sometimes count letter frequencies and start DFS from the rarer end of the word — useful in adversarial inputs.
• Mention thread safety if asked. The in-place mark mutates input; a multi-threaded solver would need per-thread copies or a separate visited matrix.

Follow-up Questions#

• What if cells can be revisited? Drop the visited mark; the search becomes infinite without a depth limit, so add i less-than-or-equal len(word).
• What if diagonal moves are allowed? Eight directions instead of four; same skeleton.
• Boggle scoring. Award points proportional to word length; record total instead of just word list.
• Multiple grids / corpus updating frequently. Keep the trie static and the grid traversal stateless; concurrent DFS by grid is trivially parallel.
• Detect a cycle / repeated path. Replace the in-place mark with a path set; useful when other constraints involve memoization on prefix.

Key Takeaways#

• Word Search is grid-DFS with backtracking; the four-direction recursion plus an in-place visited mark is the canonical FAANG template.
• Mark-and-restore (writing # and putting the original character back) saves O(m * n) memory versus a separate visited matrix.
• For multi-word search (LC 212) build a trie from the dictionary and run a single DFS; the trie prunes aggressively whenever the current prefix has no extension in the dictionary.
• Pop the terminal marker after recording a word to avoid duplicate hits when a word appears via multiple paths.
• Time complexity is O(m * n * 4^L) in the worst case but is dominated by mismatch-induced early termination on real inputs.
• This pattern powers Boggle solvers, autocomplete, mobile keyboard prediction, and crossword puzzle engines in production systems.