← ~/lc-grind/posts

#79 - Word Search

June 30, 2025

Word Search

Problem Description

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.

Example 1:


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

Example 2:


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

Example 3:


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

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Solution

1. Problem Deconstruction

Technical Restatement:
Given an m×nm \times n matrix board of characters and a string word, determine if word exists contiguously in the matrix. Contiguous means adjacent via horizontal/vertical moves (4-directional connectivity) without reusing any cell. Formally, there must exist a sequence of indices (i0,j0),(i1,j1),…,(ik−1,jk−1)(i_0, j_0), (i_1, j_1), \ldots, (i_{k-1}, j_{k-1}) where:

  • k=len(word)k = \texttt{len(word)}
  • ∀t∈[0,k−1]:board[it][jt]=word[t]\forall t \in [0, k-1]: \texttt{board}[i_t][j_t] = \texttt{word}[t]
  • ∀t:(it,jt)\forall t: (i_t, j_t) and (it+1,jt+1)(i_{t+1}, j_{t+1}) are adjacent under ∣di∣+∣dj∣=1|di| + |dj| = 1
  • All (it,jt)(i_t, j_t) are distinct

Beginner-Friendly Restatement:
Imagine a grid of letters. You start at any cell and move up, down, left, or right to adjacent cells. Can you spell the target word by collecting letters in sequence without stepping on the same cell twice?

Mathematical Formulation:
Let BB be the m×nm \times n matrix, WW the word of length LL. Define:

  • P\mathcal{P} as all paths P=[(i0,j0),…,(iL−1,jL−1)]P = [(i_0,j_0),\ldots,(i_{L-1},j_{L-1})] where:

    (it,jt)∈{0,…,m−1}×{0,…,n−1}(i_t, j_t) \in \{0,\ldots,m-1\} \times \{0,\ldots,n-1\}

    (it,jt)≠(it′,jt′)∀t≠t′(i_t, j_t) \neq (i_{t'}, j_{t'}) \quad \forall t \neq t'

    ∣it−it+1∣+∣jt−jt+1∣=1∀t<L−1|i_t - i_{t+1}| + |j_t - j_{t+1}| = 1 \quad \forall t < L-1

  • Goal: ∃P∈P\exists P \in \mathcal{P} such that:

    B[it][jt]=W[t]∀t∈[0,L−1]B[i_t][j_t] = W[t] \quad \forall t \in [0, L-1]

Constraint Analysis:

  • 1≤m,n≤61 \leq m, n \leq 6:
    • Limits solution complexity; O(mn⋅3L)O(mn \cdot 3^L) DFS is feasible since mn≤36mn \leq 36 and L≤15L \leq 15 (worst-case ≈36×314≈1.7×108\approx 36 \times 3^{14} \approx 1.7 \times 10^8 operations, acceptable in Pyton due to pruning).
    • Edge: Small grids (e.g., 1×11 \times 1) require handling single-cell words.
  • 1≤word.length≤151 \leq \texttt{word.length} \leq 15:
    • DFS depth ≤15\leq 15 avoids stack overflow.
    • Edge: Word longer than mnmn (impossible, caught by frequency check).
  • Case-sensitive letters:
    • ‘a’ ≠\neq ‘A’; must match exactly.
    • Edge: Word with letters absent in board (pruned early).

2. Intuition Scaffolding

Analogies:

  1. Real-World Metaphor (Scavenger Hunt):
    • You have a map (grid) of letters. Find a path collecting the word’s letters in order without revisiting locations.
  2. Gaming Analogy (Path Building in RPGs):
    • Like connecting runes on a magic grid to cast a spell, where each rune must be adjacent and uniquely used.
  3. Math Analogy (Graph Walk):
    • Model grid as graph G(V,E)G(V,E) where V=V= cells, E=E= adjacent cells. Solve: Is WW a label sequence of a simple path in GG?

Common Pitfalls:

  1. Missing Frequency Pruning:
    • If WW has more 'A’s than the grid, DFS wastes time.
  2. Forgetting to Unmark Cells:
    • Without backtracking cleanup, subsequent DFS calls see modified board.
  3. Terminating Early on Last Character:
    • DFS must return after matching the entire word, not just the start.
  4. Ignoring Case Sensitivity:
    • ‘a’ vs ‘A’ treated as mismatch.
  5. Optimizing Prematurely for Larger Boards:
    • Constraints allow DFS, but for larger grids (follow-up), need advanced pruning (e.g., Trie, meet-in-middle).

3. Approach Encyclopedia

Approach 1: Brute-Force DFS with Backtracking

  • Idea: For each cell matching word[0], start DFS to match word[1:] via adjacent moves, backtracking if path fails.
  • Pseudocode:
    for i in range(m):  
  for j in range(n):  
    if DFS(i, j, 0) returns True: return True  
return False  

def DFS(i, j, k):  
  if (i, j) out of bounds or board[i][j] != word[k]: return False  
  if k == len(word) - 1: return True  
  mark board[i][j] as visited  
  for each adjacent cell (ni, nj):  
    if DFS(ni, nj, k+1): return True  
  unmark board[i][j]  
  return False
  • Complexity Proof:
    • Time: O(mn⋅3L)O(mn \cdot 3^L). Each DFS call branches ≤3\leq 3 (excludes parent). LL steps per path, mnmn starting points.

      T(m,n,L)=mn×∑d=0L−13d=mn⋅3L−12∈O(mn⋅3L)T(m,n,L) = mn \times \sum_{d=0}^{L-1} 3^d = mn \cdot \frac{3^L - 1}{2} \in O(mn \cdot 3^L)

    • Space: O(L)O(L) for recursion stack (depth LL).
  • Visualization:
    Example: word = "AB", board = [["A","B"]]
Start at (0,0): 
  k=0: 'A' matches word[0] -> mark (0,0) as '#'
  Adjacent: (0,1) -> 'B' matches word[1] -> return True
Path: (0,0) → (0,1)
Board state during DFS:
  Initial: [A, B] 
  k=0:    [#, B] 
  k=1:    [#, #] (restored after True)

Approach 2: Optimized DFS with Frequency Pruning

  • Idea: Add pre-check: If any char in word exceeds its frequency in board, return False early.
  • Pseudocode:
    freq_board = count chars in board  
freq_word = count chars in word  
for char in freq_word:  
  if freq_word[char] > freq_board[char]: return False  
# Then run DFS as in Approach 1
  • Complexity Proof:
    • Time: O(mn+∣Σ∣)+O(mn⋅3L)O(mn + |\Sigma|) + O(mn \cdot 3^L), where Σ\Sigma is alphabet (52 letters). Pruning reduces LL in practice.
    • Space: O(∣Σ∣)O(|\Sigma|) for frequency counters.
  • Visualization:
    Example: word = "ZZZ", board = [["A","B"]]
freq_board: {'A':1, 'B':1}, freq_word: {'Z':3}  
'Z' count in word (3) > board (0) → return False without DFS.

4. Code Deep Dive

Optimal Solution (DFS + Frequency Pruning):

from collections import Counter

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        
        # Frequency pruning
        board_chars = [ch for row in board for ch in row]
        if Counter(word) - Counter(board_chars):  # If word has excess chars
            return False
        
        def dfs(i, j, k):
            if not (0 <= i < m and 0 <= j < n) or board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            temp, board[i][j] = board[i][j], '#'  # Mark visited
            for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                ni, nj = i + dx, j + dy
                if dfs(ni, nj, k + 1):
                    board[i][j] = temp  # Restore before returning
                    return True
            board[i][j] = temp  # Restore on failure
            return False
        
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

Line-by-Line Annotations:

  • Lines 5-7: Frequency check. Counter(word) - Counter(board_chars) is non-empty if word has chars not in board or in excess.
  • Line 9: dfs function: Checks (i,j) for word[k] match.
  • Lines 10-11: Base 1: Out-of-bounds or mismatch → fail. Base 2: Entire word matched → success.
  • Line 12: Temporarily mark board[i][j] as '#' to prevent reuse.
  • Lines 13-16: Recursively check neighbors. If any path succeeds, restore cell and propagate True.
  • Line 17: Restore cell if all neighbors fail.
  • Lines 19-22: Try DFS from every starting cell.

Edge Case Handling:

  • Example 1 ("ABCCED"):
    • Starts at (0,0), path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1). dfs(2,1,5) returns True.
  • Example 2 ("SEE"):
    • Starts at (1,3), path: (1,3)→(2,3)→(2,2). dfs(2,2,2) returns True.
  • Example 3 ("ABCB"):
    • All paths fail frequency check? No, frequencies suffice, but DFS fails → returns False.
  • Single-Letter Word: k==0 and len(word)==1 → dfs returns True at line 11.

5. Complexity War Room

Hardware-Aware Analysis:

  • Worst-case: mn=36mn=36, L=15L=15 → 36×314≈1.7×10836 \times 3^{14} \approx 1.7 \times 10^8 operations.
  • In Python, ∼107\sim 10^7 ops/sec → ∼17\sim 17 sec (worst-case, but pruning reduces this).
  • Memory: O(L)O(L) stack depth (≤15\leq 15 frames) → negligible.

Industry Comparison Table:

Approach Time Complexity Space Complexity Readability Interview Viability
Brute-Force DFS O(mn⋅4L)O(mn \cdot 4^L) O(L)O(L) 9/10 ❌ Fails L=15L=15
DFS + Pruning O(mn⋅3L)O(mn \cdot 3^L) O(L)O(L) 8/10 ✅ Optimal
DP + Bitmask O(mnL⋅2mn)O(mnL \cdot 2^{mn}) O(mn⋅2mn)O(mn \cdot 2^{mn}) 3/10 ❌ Exceeds memory

6. Pro Mode Extras

Variants:

  1. LC 79 (This Problem): Solved above.
  2. LC 212 (Word Search II):
    • Given a list of words, return all words in the board.
    • Solution: Trie + DFS. Insert words into Trie, traverse board to match Trie paths.
  3. LC 123 (Multi-Transaction Stocks):
    • Unrelated but mentioned in template; uses state machine DP.

Interview Cheat Sheet:

  • Mention First: “DFS with backtracking and frequency pruning; O(mn⋅3L)O(mn \cdot 3^L) time, O(L)O(L) space.”
  • Corner Cases:
    • Single-cell board with one-letter word.
    • word longer than mnmn.
    • Case sensitivity.
  • Optimization Hints:
    • Reverse word if suffix is rarer than prefix (empirically faster).
    • Use iterative DFS to avoid recursion limits.