Word Search: DFS backtracking that marks and unmarks its own path

Word Search is the problem that made backtracking concrete for me. Before this, backtracking felt like a general idea — try something, undo it, try the next thing. Here the grid gives it physical intuition: you are literally walking a path through cells, leaving a trail of # markers behind you, and erasing them when you back out. If that sounds obvious in retrospect, it wasn't when I first stared at a 3x4 board and had to answer "how do I avoid revisiting a cell I'm already on?"

LeetCode 79 asks: given an m x n board of characters and a string word, return true if word can be spelled out by walking horizontally or vertically through adjacent cells, using each cell at most once.

What the constraints force on you

1 <= m, n <= 6. The board is tiny. At most 36 cells. 1 <= word.length <= 15. The word fits in a 6x6 board twice over with room left.

The worst-case complexity of DFS backtracking on this problem is O(m _ n _ 4^L), where L is the word length. Plug in the actual constraint maxima: 6 _ 6 _ 4^15 = 36 * 1,073,741,824. That's around 38 billion in theory. In practice the backtracking prunes heavily — once any character mismatches, you cut the entire subtree — so real-world performance is nowhere near this upper bound. But it tells you something important: the constraint values were chosen to make backtracking viable, not comfortable. The problem setter is essentially telling you "the right approach is backtracking, and the grid is small enough that even the naive version won't time out."

If m and n were 100, backtracking would be dead and you'd need something fundamentally different (possibly a suffix-automaton approach or Aho-Corasick for the follow-up variant). At 6x6, the upper bound is just barely acceptable, and any early-exit optimization gives you real breathing room.

One more thing the constraints tell you: no special characters, only uppercase and lowercase English letters. That means you can safely use # as a sentinel for "this cell is currently in use" without ever colliding with board content. That single fact is what makes in-place marking work.

The basic backtracking approach

The structure here is the canonical choose-explore-unchoose pattern from the series. For each starting cell, you commit to it (mark it), recurse into all four neighbors, then uncommit (restore it). The recursion carries one extra parameter: how far into word you've matched so far.

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
 
        def dfs(row: int, col: int, index: int) -> bool:
            if index == len(word):
                return True
            if row < 0 or row >= rows or col < 0 or col >= cols:
                return False
            if board[row][col] != word[index]:
                return False
 
            # Mark this cell as visited for this path
            temp = board[row][col]
            board[row][col] = '#'
 
            found = (
                dfs(row - 1, col, index + 1) or
                dfs(row + 1, col, index + 1) or
                dfs(row, col - 1, index + 1) or
                dfs(row, col + 1, index + 1)
            )
 
            # Restore — critical for correctness on other starting cells
            board[row][col] = temp
            return found
 
        for i in range(rows):
            for j in range(cols):
                if dfs(i, j, 0):
                    return True
        return False

public class Solution {
    public bool Exist(char[][] board, string word) {
        int rows = board.Length;
        int cols = board[0].Length;
 
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (DFS(board, word, i, j, 0, rows, cols))
                    return true;
 
        return false;
    }
 
    private bool DFS(char[][] board, string word, int row, int col, int index, int rows, int cols) {
        if (index == word.Length) return true;
        if (row < 0 || row >= rows || col < 0 || col >= cols) return false;
        if (board[row][col] != word[index]) return false;
 
        char temp = board[row][col];
        board[row][col] = '#';
 
        bool found = DFS(board, word, row - 1, col, index + 1, rows, cols)
                  || DFS(board, word, row + 1, col, index + 1, rows, cols)
                  || DFS(board, word, row, col - 1, index + 1, rows, cols)
                  || DFS(board, word, row, col + 1, index + 1, rows, cols);
 
        board[row][col] = temp;
        return found;
    }
}

The or short-circuit in Python does something useful here: as soon as one direction returns true, we skip the remaining three. In C# the || operator does the same. This is implicit pruning — the subtree for the found path exits immediately, but the backtrack still runs (board[row][col] = temp) so the board is clean for any subsequent starting cell.

Walking through "ABCCED"

Board:

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

Word: ABCCED

The trace below uses coordinates (row, col), zero-indexed.

Start at (0,0): board[0][0]='A', word[0]='A' -> match
  Mark (0,0)='#', try neighbors, index=1
  Try (row-1,col): (-1,0) -> out of bounds, return false
  Try (row+1,col): (1,0) -> board[1][0]='S', word[1]='B' -> mismatch, return false
  Try (row,col-1): (0,-1) -> out of bounds, return false
  Try (row,col+1): (0,1) -> board[0][1]='B', word[1]='B' -> match
    Mark (0,1)='#', try neighbors, index=2
    Try (row+1,col): (1,1) -> board[1][1]='F', word[2]='C' -> mismatch
    Try (row,col+1): (0,2) -> board[0][2]='C', word[2]='C' -> match
      Mark (0,2)='#', try neighbors, index=3
      Try (row+1,col): (1,2) -> board[1][2]='C', word[3]='C' -> match
        Mark (1,2)='#', try neighbors, index=4
        Try (row+1,col): (2,2) -> board[2][2]='E', word[4]='E' -> match
          Mark (2,2)='#', try neighbors, index=5
          Try (row,col+1): (2,3) -> board[2][3]='E', word[5]='D' -> mismatch
          Try (row,col-1): (2,1) -> board[2][1]='D', word[5]='D' -> match
            Mark (2,1)='#', index=6
            index == len(word) -> return True

The DFS visualization as a decision tree:

Every time a branch hits a mismatch or a # cell, that subtree collapses immediately. The restore at each level (board[row][col] = temp) is what lets other starting cells see a clean board.

The optimized approach with frequency pruning

The basic version has one avoidable problem: it tries every cell as a starting point, even cells that can't possibly begin the word. The optimized version adds two pruning steps before the DFS loop.

First, count how many times each character appears on the board. If the word requires more occurrences of any character than the board has, return false immediately — no DFS needed.

Second, compare the frequency of the first character of word against the frequency of the last character. If the last character is rarer than the first, reverse the word and search for it backwards. This works because a path is valid in both directions — if "ABCCED" exists, then "DECBCA" exists along the same path. Starting from the rarer endpoint means fewer valid starting cells, so fewer DFS roots, so fewer total nodes visited.

from collections import Counter
 
class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
 
        # Count character frequencies on the board
        board_count: Counter[str] = Counter()
        for row in board:
            board_count.update(row)
 
        # Prune: word requires characters not present in sufficient quantity
        word_count = Counter(word)
        for ch, cnt in word_count.items():
            if board_count[ch] < cnt:
                return False
 
        # Direction heuristic: start from the rarer end
        if board_count[word[0]] > board_count[word[-1]]:
            word = word[::-1]
 
        def dfs(row: int, col: int, index: int) -> bool:
            if index == len(word):
                return True
            if row < 0 or row >= rows or col < 0 or col >= cols:
                return False
            if board[row][col] != word[index]:
                return False
 
            temp = board[row][col]
            board[row][col] = '#'
 
            found = (
                dfs(row - 1, col, index + 1) or
                dfs(row + 1, col, index + 1) or
                dfs(row, col - 1, index + 1) or
                dfs(row, col + 1, index + 1)
            )
 
            board[row][col] = temp
            return found
 
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0] and dfs(i, j, 0):
                    return True
        return False

public class Solution {
    public bool Exist(char[][] board, string word) {
        int rows = board.Length;
        int cols = board[0].Length;
 
        // Count board character frequencies
        var boardCount = new Dictionary<char, int>();
        foreach (var row in board)
            foreach (char c in row)
                boardCount[c] = boardCount.GetValueOrDefault(c, 0) + 1;
 
        // Prune: early exit if word characters unavailable
        var wordCount = new Dictionary<char, int>();
        foreach (char c in word) {
            wordCount[c] = wordCount.GetValueOrDefault(c, 0) + 1;
            if (!boardCount.ContainsKey(c) || wordCount[c] > boardCount[c])
                return false;
        }
 
        // Direction heuristic: reverse word to start from rarer character
        if (boardCount[word[0]] > boardCount[word[word.Length - 1]]) {
            char[] arr = word.ToCharArray();
            Array.Reverse(arr);
            word = new string(arr);
        }
 
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (board[i][j] == word[0] && DFS(board, word, i, j, 0, rows, cols))
                    return true;
 
        return false;
    }
 
    private bool DFS(char[][] board, string word, int row, int col, int index, int rows, int cols) {
        if (index == word.Length) return true;
        if (row < 0 || row >= rows || col < 0 || col >= cols) return false;
        if (board[row][col] != word[index]) return false;
 
        char temp = board[row][col];
        board[row][col] = '#';
 
        bool found = DFS(board, word, row - 1, col, index + 1, rows, cols)
                  || DFS(board, word, row + 1, col, index + 1, rows, cols)
                  || DFS(board, word, row, col - 1, index + 1, rows, cols)
                  || DFS(board, word, row, col + 1, index + 1, rows, cols);
 
        board[row][col] = temp;
        return found;
    }
}

The frequency check costs O(m * n + L) time and O(1) space if you use a fixed-size array for the 52 possible characters (26 lowercase + 26 uppercase). It pays for itself immediately on any board where the word contains a character that appears only once but the word needs it twice.

The reversal heuristic is trickier to internalize. Imagine the board has 20 'A' cells and 1 'Z' cell, and the word is "AZ...". Starting from all 20 'A' cells, most DFS paths will reach a dead end quickly, but you still initialize 20 recursion trees. Reverse to "...ZA" and you start from exactly 1 cell. The DFS bodies are identical — you just gave yourself 19 fewer root calls.

Edge cases that matter

Single cell, single character word. board = [["A"]], word = "A". The DFS enters at (0,0), index=0 matches, marks the cell, recurses, immediately hits index == 1 == len(word) and returns true. Then the restore runs. This works, and it's worth checking explicitly because the index == len(word) base case must fire before any bounds check.

Word longer than the board has cells. If word.length > m * n, no path through the board can spell it out — each cell can be used once. The optimized version catches this implicitly through the frequency check (at least one character would be needed more times than it appears). The basic version doesn't catch it early, but DFS will still return false correctly because paths can't loop back to visited cells.

All cells identical, word repeats that character. board = [["A","A"],["A","A"]], word = "AAAA". The DFS can snake through the board without revisiting cells because the # marker blocks backtracking to already-claimed cells. A 2x2 board with 4 'A' cells spells "AAAA" exactly once (there's only one Hamiltonian path through a 2x2 grid, up to rotation). The in-place marker handles this correctly without extra logic.

Word not in board at all. The DFS exhausts all starting cells and all paths from each. false is returned after all of them fail. This is the worst case for performance — no early termination from finding the word.

Word's last character is identical to first character, rare. This is where the reversal heuristic can hurt if implemented carelessly: word[0] == word[-1] means reversing the word produces a different starting character check, but boardCount[word[0]] == boardCount[word[-1]] so the condition boardCount[word[0]] > boardCount[word[-1]] is false and no reversal happens. Safe.

Complexity and what to actually ship

Both have the same asymptotic time bound. The space difference is K — the number of distinct characters on the board, which in the worst case is 52 but in practice is small. L is the word length, which dominates the call stack depth.

The big-O bound looks alarming until you remember the 4^L factor assumes each cell always has 4 viable neighbors. That's only true for cells deep in the interior of a very large board. On a 6x6 grid, corner cells have 2 neighbors, edge cells have 3. At depth k into the word, the candidate set shrinks as the path backs into itself and hits # markers. The actual node count explored is dramatically less than the theoretical worst case.

I'd ship the optimized version for any production context, but not primarily for the frequency pruning — for the reversal heuristic. The frequency check is a nice O(m*n) preflight that costs almost nothing, but the reversal is the one that matters when the word's terminal character is much rarer than its initial character, which happens in real datasets far more often than the clean examples suggest. On a 6x6 board it might shave 30% of DFS calls in pathological cases.

The basic version is the right version to write first, understand completely, and explain in an interview. Once it's correct, adding the two optimizations is mechanical.

In-place marking vs a separate visited matrix

The alternative approach uses a separate bool[m][n] visited matrix instead of mutating the board. Both are correct. The trade-off:

In-place marking uses O(L) space (just the call stack), treats the sentinel # as part of the value domain, and mutates the input. That last point can be a problem if the caller expects the board to be unchanged after the call. In an interview context where the function signature passes board and you're expected to leave it intact, you'd want the visited matrix approach.

The visited matrix uses O(m * n + L) space — a full boolean grid plus the call stack. It doesn't mutate the input, which is cleaner if you're writing a library. The code is nearly identical; just replace board[row][col] = '#' with visited[row][col] = true and the bounds check accordingly.

For LeetCode submissions, in-place marking is the conventional choice and restores the board correctly, so the function appears to have left the board untouched by the time it returns. I'd call this acceptable for competitive programming but worth noting in production code.

Where this sits in the series and what comes next

This is the fourth problem in the backtracking series, and it's where the "grid" variant of backtracking first appears. The earlier problems (Subsets, Combinations, Permutations) all work on a flat list with a simple index tracking which elements remain eligible. Here the state is spatial — you track which cells are on the current path, not which array indices you've passed.

The decision tree here branches on direction rather than element selection. Each node in the tree is a (row, col, index) triple. The branching factor is at most 4. The depth is word.length. That framing — decision tree with bounded branching and finite depth — applies to both the 1D list problems and the 2D grid problems; the grid just makes it visually obvious.

Four problems that build on this same shape:

LeetCode 212 — Word Search II. Same grid, but find all words from a given dictionary simultaneously. Naive: run LeetCode 79 once per word. Better: build a Trie of all words, DFS the grid once, check each cell against the Trie prefix. The twist is that the DFS now has to report all paths, not stop at the first match, and the Trie is the pruning mechanism instead of a character frequency check.

LeetCode 200 — Number of Islands. DFS on a grid again, but the goal is to count connected components, not match a string. No backtracking needed — you mark cells permanently visited because you never need to reuse them. Understanding Word Search makes Number of Islands feel almost trivial in comparison, because you don't need to undo anything.

LeetCode 130 — Surrounded Regions. DFS to identify regions that touch the border, then flip everything that doesn't. Same grid traversal mechanics, but the search target is topological (connectivity to border) rather than sequential (character matching).

LeetCode 329 — Longest Increasing Path in a Matrix. DFS on a grid where the constraint is that each step must be strictly larger than the previous. No visited marking needed because the strictly-increasing constraint prevents revisiting. Memoization turns this from exponential into O(m * n). It's the natural next problem after Word Search if you want to see what happens when you remove the "can't revisit" constraint and replace it with a value constraint.