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.

Examples

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.

Thinking Process

  1. DFS with Backtracking: Explore all paths, restore state after exploring
  • DFS explores one branch fully before backtracking.
  • Mark visited nodes to avoid cycles on graphs.
  • Return aggregated results from children to the parent.
Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

Solution: Backtracking with DFS

class Solution:
    def exist(self, board, word):
        rows = len(board)
        cols = len(board[0])

        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        for r in range(rows):
            for c in range(cols):
                if self.backtrack(board, word, r, c, 0, rows, cols, dirs):
                    return True

        return False

    def backtrack(self, board, word, row, col, idx, rows, cols, dirs):
        if idx == len(word):
            return True

        if (row < 0 or row >= rows or
            col < 0 or col >= cols or
            board[row][col] != word[idx]):
            return False

        temp = board[row][col]
        board[row][col] = '#'

        for dr, dc in dirs:
            if self.backtrack(board, word, row + dr, col + dc, idx + 1, rows, cols, dirs):
                return True

        board[row][col] = temp
        return False

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: 1. DFS with Backtracking: Explore all paths, restore state after exploring

How the code works:

  1. DFS with Backtracking: Explore all paths, restore state after exploring
    • DFS explores one branch fully before backtracking.
    • Mark visited nodes to avoid cycles on graphs.
    • Return aggregated results from children to the parent.

Walkthrough — input board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED", expected output true:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

Algorithm Explanation:

  1. Main Function (Lines 3-12):
    • Store rows and cols dimensions
    • For each cell (r, c): Try starting word search from that cell
    • If any starting position finds the word, return true
    • Otherwise, return false
  2. Backtrack Function (Lines 17-28):
    • Base Case (Line 18): If idx == word.length(), we’ve matched entire word → return true
    • Validation (Lines 19-21):
      • Check bounds: row and col within grid
      • Check character match: board[row][col] == word[idx]
      • If invalid, return false
    • Mark as Visited (Line 23): Set board[row][col] = '#' to prevent revisiting
    • Explore Directions (Lines 24-26):
      • Try all 4 directions: right, left, down, up
      • If any direction finds the word, return true immediately
    • Backtrack (Line 27): Restore original character board[row][col] = word[idx]
    • Return (Line 28): Return false if no path found

Why This Works:

  • DFS Exploration: Explores all possible paths from each starting position
  • Visited Marking: Using '#' prevents revisiting the same cell in current path
  • Backtracking: Restoring cell value allows exploring other paths that might use this cell
  • Early Termination: Returns true as soon as word is found (no need to explore further)
  • Direction Array: Clean way to iterate through 4 directions

Example Walkthrough:

For board = [["A","B","C"],["S","F","C"]], word = "ABCCED":

Starting from (0,0) with word "ABCCED":

backtrack(0, 0, 0):
  idx=0, board[0][0]='A' == word[0]='A' ✓
  Mark: board[0][0]='#'
  
  Try direction (0,1): backtrack(0, 1, 1)
    idx=1, board[0][1]='B' == word[1]='B' ✓
    Mark: board[0][1]='#'
    
    Try direction (0,2): backtrack(0, 2, 2)
      idx=2, board[0][2]='C' == word[2]='C' ✓
      Mark: board[0][2]='#'
      
      Try direction (1,2): backtrack(1, 2, 3)
        idx=3, board[1][2]='C' == word[3]='C' ✓
        Mark: board[1][2]='#'
        
        Try direction (1,1): backtrack(1, 1, 4)
          idx=4, board[1][1]='F' != word[4]='E' ✗
        Try direction (0,2): board[0][2]='#' ✗ (visited)
        Try direction (2,2): Out of bounds ✗
        Try direction (1,0): backtrack(1, 0, 4)
          idx=4, board[1][0]='S' != word[4]='E' ✗
        Backtrack: board[1][2]='C'
        
      Try direction (1,1): backtrack(1, 1, 3)
        idx=3, board[1][1]='F' != word[3]='C' ✗
      Try direction (0,1): board[0][1]='#' ✗ (visited)
      Try direction (1,3): Out of bounds ✗
      Backtrack: board[0][2]='C'
    
    Try direction (1,1): backtrack(1, 1, 2)
      idx=2, board[1][1]='F' != word[2]='C' ✗
    Try direction (0,0): board[0][0]='#' ✗ (visited)
    Try direction (1,2): backtrack(1, 2, 2)
      idx=2, board[1][2]='C' == word[2]='C' ✓
      Mark: board[1][2]='#'
      
      Try direction (1,3): Out of bounds ✗
      Try direction (1,1): backtrack(1, 1, 3)
        idx=3, board[1][1]='F' != word[3]='C' ✗
      Try direction (2,2): Out of bounds ✗
      Try direction (0,2): backtrack(0, 2, 3)
        idx=3, board[0][2]='C' == word[3]='C' ✓
        Mark: board[0][2]='#'
        
        Try direction (0,3): Out of bounds ✗
        Try direction (0,1): board[0][1]='#' ✗ (visited)
        Try direction (1,2): board[1][2]='#' ✗ (visited)
        Try direction (-1,2): Out of bounds ✗
        Backtrack: board[0][2]='C'
      Backtrack: board[1][2]='C'
    Backtrack: board[0][1]='B'
  Backtrack: board[0][0]='A'

No path found from (0,0). Try other starting positions...

Note: The actual path for “ABCCED” might not exist in this small example. The algorithm correctly explores all possibilities.

Complexity Analysis:

  • Time Complexity: O(m × n × 4^L) where L is word length
    • For each of m × n starting positions
    • Explore up to 4^L paths (4 directions, L depth)
    • With pruning (character mismatch), actual complexity is better
  • Space Complexity: O(L)
    • Recursion stack depth: at most L (word length)
    • No additional data structures (modifies board in-place)

      Common Mistakes

  1. Single character word: word = "A" → return true if ‘A’ exists in board
  2. Word longer than board: Impossible, but handled by bounds checking
  3. All cells same character: board = [["A","A"],["A","A"]], word = "AAA" → return true
  4. No matching path: Return false after exploring all possibilities

  5. Word not found: Return false

  6. Not restoring cell value: Forgetting to backtrack causes incorrect results
  7. Wrong visited marking: Not marking before recursion or marking incorrectly
  8. Missing bounds check: Accessing out-of-bounds indices
  9. Wrong character comparison: Comparing before marking as visited
  10. Not checking all starting positions: Only checking first cell

Key Takeaways

  1. DFS with Backtracking: Explore all paths, restore state after exploring
  2. In-Place Marking: Use '#' to mark visited cells (no extra visited array needed)
  3. Early Termination: Return true immediately when word is found
  4. Direction Array: Clean iteration through 4 directions
  5. Boundary Checking: Check bounds and character match before recursing

References

Template Reference