Skip to content

106 — Word Search

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

106 — Word Search

LeetCode 79 · Medium. Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same cell may not be used more than once.

🍽️ Intuition

Chapter 18's worked example already sketched this exact problem to demonstrate that a grid can play the role of "candidates" in the generic backtracking template — a cell's four neighbors are its branches, and "mark visited, then un-mark on the way back out" is the choose/un-choose step. This chapter goes one level deeper on the one design decision that example glossed over: when do you check whether a cell actually matches the letter you need? Checking early versus checking late is the entire difference between a search that behaves reasonably and one that explores wildly more of the grid than it needs to.

🚩 Pattern-Recognition Cue

"Word must be constructed from sequentially adjacent cells" combined with "the same cell may not be used more than once" is a 2D grid-DFS cue: adjacency defines the branches (up/down/left/right), and the "not reused" constraint means each path through the grid needs its own notion of which cells are currently marked, undone the instant that path is abandoned.

🐢 Brute Force

Explore every simple path (no repeated cells) of exactly word.count cells from every starting position, and only compare the fully-built path against word once the path reaches the target length — characters are never checked mid-search, so wrong-letter paths get explored just as deeply as promising ones.

func existBruteForce(_ board: [[Character]], _ word: String) -> Bool {
    let target = Array(word)
    let rows = board.count
    let cols = board[0].count
    var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
    var path: [Character] = []
    let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    func explore(_ row: Int, _ col: Int) -> Bool {
        if path.count == target.count {
            return path == target   // only compared once the FULL path is built
        }
        guard row >= 0, row < rows, col >= 0, col < cols, !visited[row][col] else { return false }

        visited[row][col] = true
        path.append(board[row][col])

        var found = false
        for (dr, dc) in directions {
            if explore(row + dr, col + dc) {
                found = true
                break
            }
        }

        path.removeLast()
        visited[row][col] = false
        return found
    }

    for r in 0..<rows {
        for c in 0..<cols {
            if explore(r, c) { return true }
        }
    }
    return false
}

// smoke test
let bfBoard: [[Character]] = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"]
]
print(existBruteForce(bfBoard, "ABCCED"))   // true
print(existBruteForce(bfBoard, "SEE"))      // true
print(existBruteForce(bfBoard, "ABCB"))     // false

Big-O: O(rows · cols · 4^L) where L = word.count — every starting cell explores up to 4^L simple paths of that length regardless of whether the letters along the way ever matched word. O(L) extra space for path and the visited grid.

🚀 Optimal

Check the character match at every single step, and return false immediately the instant a cell's letter doesn't match — a mismatched branch is abandoned after one comparison instead of after building the rest of the path around it.

func exist(_ board: [[Character]], _ word: String) -> Bool {
    let target = Array(word)
    let rows = board.count
    let cols = board[0].count
    var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)

    func backtrack(_ row: Int, _ col: Int, _ index: Int) -> Bool {
        if index == target.count { return true }
        guard row >= 0, row < rows, col >= 0, col < cols,
              !visited[row][col], board[row][col] == target[index] else {
            return false   // prune immediately on mismatch — no further exploration down this path
        }

        visited[row][col] = true
        let found = backtrack(row + 1, col, index + 1)
            || backtrack(row - 1, col, index + 1)
            || backtrack(row, col + 1, index + 1)
            || backtrack(row, col - 1, index + 1)
        visited[row][col] = false

        return found
    }

    for r in 0..<rows {
        for c in 0..<cols {
            if backtrack(r, c, 0) { return true }
        }
    }
    return false
}

// smoke test — same cases as the brute force
print(exist(bfBoard, "ABCCED"))   // true
print(exist(bfBoard, "SEE"))      // true
print(exist(bfBoard, "ABCB"))     // false

Big-O: O(rows · cols · 4^L) in the theoretical worst case (a grid where every cell could plausibly extend the word) — the same bound as the brute force, since no amount of pruning changes what happens when nothing is actually prunable. In every realistic case, though, the character check aborts a branch after its very first mismatched letter, instead of building the rest of that dead path anyway.

🔑 The Key Insight

This is the one chapter in this batch where the optimal version doesn't win on paper — its worst-case Big-O matches the brute force's, because a pathological grid where every cell shares the word's first letter genuinely forces exploring nearly every path either way. The real win is in the typical case: the moment board[row][col] != target[index], the optimal version's guard fails and that branch dies on the spot, while the brute-force version keeps extending that same doomed path all the way to length L before finally noticing it never matched. Pruning early doesn't always change the worst-case bound — but it changes how often you actually pay that worst case.

🔗 Related Chapters

  • DFS and Backtracking — this chapter's own worked example; this chapter makes the "check as you go" pruning decision explicit and gives it a brute-force counterpoint.
  • Matrix Traversal — the four-directional neighbor exploration and bounds-checking are matrix traversal fundamentals applied with backtracking's mark/unmark discipline layered on top.
  • Arrays and Strings — word is converted to [Character] up front so indexing into it is O(1), rather than repeatedly indexing into a Swift String.

🧸 Memory Sentence

Word Search is grid DFS with a ball of string — check the letter the instant you step onto a cell, and the moment it's wrong, reel back immediately instead of walking the rest of a path that was already doomed.

✅ Check Your Understanding

  1. Both existBruteForce and exist mark and unmark visited cells. Why does that alone not make the brute-force version "pruned" — what's still missing?
  2. Why does exist check board[row][col] == target[index] as part of the same guard that checks grid bounds, rather than as a separate if after the bounds check?
  3. Construct a small grid where the brute-force version and the optimal version actually do the same amount of work in the worst case. What has to be true about that grid for that to happen?

⬅️ Previous: Combination Sum II · Next: Palindrome Partitioning ➡️

Clone this wiki locally