LeetEye LeetEye
Hard Backtracking ~5 min

Word Search

backtracking word-search

Problem

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
Key Insight

DFS from each cell that matches first letter. Mark visited cells to avoid reuse. Backtrack on failure.

DFS from each cell matching word[0]. At each step: check bounds, check match, mark visited, explore 4 directions, unmark (backtrack). Return True if all matched.

How to Approach This Problem

Pattern Recognition: When you see keywords like word search backtracking, think Backtracking.

Step-by-Step Reasoning

1 We start DFS from:
Answer: Any cell matching word[0]
Word could start anywhere. But only cells matching first character are valid starts.
2 From each cell, we can move to:
Answer: All 4 adjacent cells (up, down, left, right)
"Adjacent" = horizontal or vertical neighbors.
3 To prevent using the same cell twice:
Answer: Mark it temporarily during DFS
Mark during exploration, unmark during backtrack. Each path has its own visited state.
4 At cell (r,c) with word index i, we proceed if:
Answer: Both A and C
Cell must match current character AND not be already used in this path.
5 We return True when:
Answer: We've matched all characters of word
index == len(word) means we've matched every character.
6 When a path fails (no valid continuation):
Answer: Return False and let parent try another direction
Backtrack to previous cell, try other directions. Classic DFS.

Solution

def exist(board: List[List[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    
    def dfs(r, c, index):
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[index]:
            return False
        
        # Mark visited
        temp = board[r][c]
        board[r][c] = &#039;#'
        
        # Explore 4 directions
        found = (dfs(r+1, c, index+1) or dfs(r-1, c, index+1) or
                 dfs(r, c+1, index+1) or dfs(r, c-1, index+1))
        
        # Backtrack
        board[r][c] = temp
        return found
    
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Complexity Analysis

Time O(m * n * 4^L)
Space O(L)

Master This Pattern

Build intuition with interactive MCQs. Practice Backtracking problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye