Word Search | Leetcode 79

Welcome to our deep dive on Word Search (Leetcode 79). This problem is the definitive introduction to Backtracking on a 2D Matrix grid, a pattern essential for technical interviews.

Problem Statement

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: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" => Output: true

Approach: Backtracking DFS O(N * 3^L)

To find a specific word on a large grid, we logically scan the entire grid for the very first letter of the target word. If we find that starting letter, we initiate a Depth-First Search (DFS) exploring all four adjacent orthogonal directions (Up, Down, Left, Right) to find the next sequential letter.

If a path fails (e.g., hits a dead-end or the wrong letter), we backtrack by undoing our steps and exploring alternate routes.

Because we cannot reuse physical cells in the same path, we must temporarily mark cells as "visited" (often by replacing the character with # to save space), and then critically restore them when backtracking.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        
        def dfs(r, c, i):
            if i == len(word):
                return True
            
            if (r < 0 or c < 0 or
                r >= rows or c >= cols or 
                board[r][c] != word[i] or
                board[r][c] == '#'):
                return False
                
            temp = board[r][c]
            board[r][c] = '#' # Mark as visited safely
            
            # Explore all 4 adjacent directions
            res = (dfs(r + 1, c, i + 1) or
                   dfs(r - 1, c, i + 1) or
                   dfs(r, c + 1, i + 1) or
                   dfs(r, c - 1, i + 1))
                   
            board[r][c] = temp # Backtrack cleanly
            
            return res
            
        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True
                    
        return False

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (79)