Domain 2MediumCORE

Word Search

We are given an $m times n$ grid of characters and a target string, word. The goal is to determine if we can form this word by traversing adjacent cells (horizontally or vertically) without reusing any cell within a single path.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Backtracking

79. Word Search

Model: qwen3.5:9b
Topics: Array,Backtracking
FAANG asked: 1
Acceptance rate: 37.1%


Problem Breakdown

We are given an m×nm \times n grid of characters and a target string, word. The goal is to determine if we can form this word by traversing adjacent cells (horizontally or vertically) without reusing any cell within a single path.

Inputs:

  • A 2D list (board) representing the character map.
  • A string (word).

Outputs:

  • Boolean True if found, False otherwise.

Implicit Constraints & Edge Cases:

  1. Empty Inputs: While constraints say m,n≥1m,n \ge 1, robust code should handle empty board or word gracefully (returning False).
  2. Word Length vs Grid Size: If the length of word exceeds total cells in grid, it’s impossible; we can prune early here for optimization.
  3. Character Frequency Mismatch: If a character required by word does not exist on the board at all (or appears fewer times than needed), return False immediately. This is crucial for larger boards as mentioned in the follow-up.

Intuition

A brute-force approach would be to try every cell as a starting point and check if it matches the first letter of word. If it does, we explore its neighbors recursively.

However, simply checking all paths without backtracking leads to infinite loops or incorrect results because once we move from one cell to another in our path, that previous cell cannot be used again for the current word search attempt (though it can be a start point for a different attempt).

The key insight is Depth First Search (DFS) with Backtracking.

  1. We iterate through every cell (i,j)(i, j) on the board to see if board[i][j] == word[0].
  2. If there’s a match, we initiate a DFS from that position.
  3. During DFS, for each step kk in the path:
    • Mark current cell as visited (to prevent reuse).
    • Recursively check valid neighbors (up/down/left/right) against word[k+1].
    • If recursion returns True, propagate success up.
  4. Backtrack: After returning from a recursive call, we must unmark the cell so it can be used in other paths starting at different branches or for subsequent search attempts if needed (though typically once visited in current path, we revert state).

Approach

  1. Pre-check Optimization: Before diving into recursion, verify that every character required by word exists on the board with sufficient frequency. If not, return False immediately. This is a significant pruning step for larger boards.
  2. Iterate Start Points: Loop through all cells (r,c)(r, c) in the grid.
  3. DFS Function (dfs(r, c)):
    • Base Case: If current index matches word length minus one (last char), return True.
    • Mark (r, c) as visited to avoid cycles/reuse within this path. A common trick is modifying the board temporarily or using a separate visited set/matrix. I will use a temporary modification of the board for O(1)O(1) space overhead per call stack frame relative to recursion depth (though technically modifies input state).
    • Recursive Step: Check all 4 neighbors (nr,nc)(nr, nc). If valid and not visited and match character at word[index + 1], recurse.
    • Backtrack: Restore the cell’s original value after returning from recursive calls so other paths can use it.
  4. Result: Return True if any DFS call returns success; otherwise False.

Complexity Analysis

  • Time Complexity: O(m⋅n⋅k)O(m \cdot n \cdot k) in practice, where mm is rows, nn is columns, and kk is word length. In the worst case without pruning (e.g., all characters same), it can approach exponential time relative to path depth (4k4^k). However, with character frequency checks and visited tracking per path, we effectively bound exploration significantly better than raw brute force on a graph of size (m⋅n)(m \cdot n).
  • Space Complexity: O(k)O(k) for the recursion stack depth (where kk is word length), plus O(mn)O(mn) if using an explicit visited matrix. If modifying the board, space drops to just the call stack overhead (O(k)O(k)).

Solution

from typing import List

def exist(board: List[List[str]], word: str) -> bool:
    m, n = len(board), len(board[0])
    
    # Optimization 1: Check character frequency counts for pruning on larger boards.
    from collections import Counter
    board_counts = Counter(char for row in board for char in row)
    word_counts = Counter(word)
    
    if not all(count <= board_counts[char] for count, char in word_counts.items()):
        return False

    def dfs(r: int, c: int, index: int) -> bool:
        # Base case: found the end of the word
        if index == len(word):
            return True
        
        current_char = board[r][c]
        
        # Mark as visited by temporarily changing value to avoid reuse in this path
        original_val = board[r][c]
        board[r][c] = '#' 
        
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            # Check bounds and if neighbor matches next char of word
            if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == word[index]:
                if dfs(nr, nc, index + 1):
                    return True
        
        # Backtrack: Restore original value for other paths to use this cell
        board[r][c] = original_val
        
        return False

    # Iterate through every cell as a potential starting point
    for r in range(m):
        for c in range(n):
            if dfs(r, c, 0):
                return True
                
    return False

Edge Cases Handled

  • Word longer than grid: The DFS naturally terminates when index reaches word length. If the path is too short to match full string before hitting bounds or mismatches, it returns False. An explicit check for total cell count vs word length could be added but isn’t strictly necessary given recursion depth limits.
  • No matching first character: The outer loop checks every start point; if none match word[0], the function exhausts all possibilities and returns False at the end.
  • Grid boundaries: Bounds checking (if 0 <= nr < m ...) prevents index errors when accessing neighbors of edge cells.
  • Path reuse prevention: The board modification (setting to ’#’) ensures that a cell used in one branch of recursion is not reused within that specific path, satisfying the “same letter cell may not be used more than once” constraint for the current word instance.