LeetCode 79: Word Search Solution in Python Explained

Problem Statement

LeetCode 79, Word Search, is a medium-level problem where you’re given an (m \times n) grid of characters board and a string word. Your task is to determine if word exists in the grid by forming a sequence of adjacent cells (horizontally or vertically, not diagonally), without reusing any cell. Return true if the word can be found, false otherwise.

Constraints

  • m == board.length: Number of rows.
  • n == board[i].length: Number of columns.
  • 1 <= m, n <= 6: Grid dimensions are between 1 and 6.
  • 1 <= word.length <= 15: Word length is between 1 and 15.
  • board and word consist of uppercase and lowercase English letters.

Example

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation: Path: A(0,0) -> B(0,1) -> C(0,2) -> C(1,2) -> E(1,3) -> D(2,1).

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation: Path: S(1,0) -> E(1,1) -> E(2,1).

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Explanation: No path forms "ABCB" without reusing cells.

Understanding the Problem

How do you solve LeetCode 79: Word Search in Python? For board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] and word = "ABCCED", determine if "ABCCED" can be formed by a path—here, it’s true via A-B-C-C-E-D. We need to search the grid, exploring adjacent cells, without reusing any, suggesting a depth-first search (DFS) approach. We’ll explore two solutions: a DFS with Backtracking Solution (optimal and primary) and an Alternative with Visited Set (similar but using extra space). The DFS method runs in O(m * n * 4^L) time with O(L) space, where (L) is the word length.

Solution 1: DFS with Backtracking Approach (Primary)

Explanation

Use DFS to explore all possible paths from each cell, backtracking by temporarily marking visited cells (e.g., with a special character) and restoring them. Start at each cell matching the word’s first character, recursively check adjacent cells for the next character, and continue until the word is found or all paths are exhausted.

Here’s a flow for board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED":

Start at (0,0): "A"
-> (0,1): "AB"
-> (0,2): "ABC"
-> (1,2): "ABCC"
-> (1,3): "ABCCE"
-> (2,1): "ABCCED", found
  1. Iterate Starting Points.
  • Check each cell for word[0].
  1. DFS with Backtracking.
  • Explore neighbors, mark visited, restore on backtrack.
  1. Check Word Match.
  • Return true if word is fully matched.
  1. Return Result.

Step-by-Step Example

Example 1: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

We need true.

  • Goal: Find "ABCCED" in the grid.
  • Result for Reference: true.
  • Start: m = 3, n = 4, word = "ABCCED".
  • Step 1: Start at (0,0) = 'A'.
    • pos = 1, mark (0,0), check neighbors:
      • (0,1) = 'B', pos = 2, mark.
      • (0,2) = 'C', pos = 3, mark.
      • (1,2) = 'C', pos = 4, mark.
      • (1,3) = 'E', pos = 5, mark.
      • (2,1) = 'D', pos = 6, len = 6, found, return true.
  • Step 2: No need to check others since found.
  • Finish: Return true.

Example 2: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

We need true.

  • Start: Check (1,0) = 'S'.
    • pos = 1, mark (1,0).
    • (1,1) = 'F', fail.
    • (2,0) = 'A', fail.
    • (0,0) = 'A', fail.
    • (1,2) = 'C', fail, backtrack.
  • Step 2: Check (1,3) = 'S'.
    • pos = 1, mark (1,3).
    • (1,2) = 'C', fail.
    • (2,3) = 'E', pos = 2, mark.
      • (2,2) = 'E', pos = 3, len = 3, found, return true.
  • Finish: Return true.

How the Code Works (DFS with Backtracking)

Here’s the Python code with line-by-line explanation:

def exist(board: list[list[str]], word: str) -> bool:
    # Line 1: Get dimensions
    m, n = len(board), len(board[0])

    # Line 2: DFS helper function
    def dfs(i: int, j: int, pos: int) -> bool:
        # Line 3: Base cases
        if pos == len(word):
            return True
        if (i < 0 or i >= m or j < 0 or j >= n or 
            board[i][j] != word[pos]):
            return False

        # Line 4: Mark current cell and explore neighbors
        temp = board[i][j]
        board[i][j] = '#'  # Mark as visited
        directions = [(0,1), (1,0), (0,-1), (-1,0)]  # Right, down, left, up
        for di, dj in directions:
            if dfs(i + di, j + dj, pos + 1):
                return True

        # Line 5: Backtrack by restoring cell
        board[i][j] = temp
        return False

    # Line 6: Check each starting point
    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0] and dfs(i, j, 0):
                return True

    # Line 7: Word not found
    return False

Alternative: Visited Set Approach

Explanation

Use DFS with a visited set to track explored cells, avoiding reuse without modifying the board. Explore from each starting point, checking adjacent cells, and backtrack by removing cells from the set.

  1. Initialize Visited Set.
  2. DFS with Set.
  • Track visited cells, explore neighbors.

3. Return Result.

Step-by-Step Example (Alternative)

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

  • Start: Check (1,3) = 'S'.
    • visited = {(1,3)}, pos = 1.
    • (2,3) = 'E', visited = {(1,3),(2,3)}, pos = 2.
    • (2,2) = 'E', visited = {(1,3),(2,3),(2,2)}, pos = 3, found.
  • Finish: Return true.

How the Code Works (Visited Set)

def existSet(board: list[list[str]], word: str) -> bool:
    # Line 1: Get dimensions
    m, n = len(board), len(board[0])

    # Line 2: DFS helper with visited set
    def dfs(i: int, j: int, pos: int, visited: set[tuple[int,int]]) -> bool:
        if pos == len(word):
            return True
        if (i < 0 or i >= m or j < 0 or j >= n or 
            (i,j) in visited or board[i][j] != word[pos]):
            return False

        visited.add((i,j))
        directions = [(0,1), (1,0), (0,-1), (-1,0)]
        for di, dj in directions:
            if dfs(i + di, j + dj, pos + 1, visited):
                return True

        visited.remove((i,j))
        return False

    # Line 3: Check each starting point
    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0] and dfs(i, j, 0, set()):
                return True

    # Line 4: Word not found
    return False

Complexity

  • DFS with Backtracking:
    • Time: O(m * n * 4^L) – Explore 4 directions up to word length \(L\) from each cell.
    • Space: O(L) – Recursion stack.
  • Visited Set:
    • Time: O(m * n * 4^L) – Same exploration.
    • Space: O(m * n) – Visited set size.

Efficiency Notes

DFS with Backtracking is O(m * n * 4^L) time and O(L) space, optimal for LeetCode 79 as it modifies the board in-place. Visited Set is same time but O(m * n) space, less space-efficient but avoids board modification.

Key Insights

Tips to master LeetCode 79:

  • DFS: Explore all paths from each start.
  • Backtracking: Mark/unmark cells to avoid reuse.
  • Directions: Check 4 neighbors systematically.

Additional Example

For board = [["A","B"],["C","D"]], word = "ABCD":

  • Goal: true.
  • DFS: A-B-C-D path, return true.
  • Result: true.

Edge Cases

  • Single Cell: [["A"]], "A" – Return true.
  • No Match: [["A"]], "B" – Return false.
  • Full Grid: \(6 \times 6\), long word – Search efficiently.

Final Thoughts

The DFS with Backtracking solution is a strong pick for LeetCode 79 in Python—efficient, in-place, and intuitive, with the Visited Set approach as a clear alternative. For a related challenge, try LeetCode 78: Subsets to switch to combinations! Ready to search? Solve LeetCode 79 on LeetCode now and test it with [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] and "ABCCED" to master word searching. Dive in and trace that path!