Cracking LeetCode 79: Word Search

Mastering LeetCode 79: The Word Search Challenge

Have you ever found yourself staring at a grid of letters, trying to spell out a word? That's precisely the essence of LeetCode Problem 79: Word Search. It's a classic algorithmic puzzle that tests your ability to navigate a grid, making it an excellent exercise for honing your Depth-First Search (DFS) and backtracking skills.

This problem isn't just a technical exercise; it's a fundamental pattern that appears in many real-world scenarios, from game development to pathfinding. Let's break down how to conquer it.

Understanding the LeetCode 79 Problem

The challenge asks us to determine if a given word exists in a 2D board of characters. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring. Crucially, the same letter cell may not be used more than once.

Example:

Consider the board:

[['A','B','C','E'],
 ['S','F','C','S'],
 ['A','D','E','E']]

And the word: "ABCCED"

The expected output is true because we can find 'A' at (0,0), 'B' at (0,1), 'C' at (0,2), 'C' at (1,2), 'E' at (2,3), and 'D' at (1,1). Notice how we traversed from (0,2) to (1,2) for the second 'C'.

Key constraints usually include the board dimensions and the length of the word. Both are typically small enough for exponential-time solutions involving backtracking to pass within limits.

The Intuition: Exploring Paths with DFS

How do we begin to search for a word? A brute-force approach might try to list every possible path starting from every cell, which quickly becomes unmanageable. The key insight lies in using a graph traversal algorithm: Depth-First Search (DFS).

When we find the first letter of our word on the board, we can start a "search path" from that cell. From there, we need to explore all four possible directions (up, down, left, right) for the next letter in our word. If we find the next letter, we continue the path. If not, or if we hit a dead end, we need to "backtrack" and try a different path. This recursive exploration is the heart of DFS and backtracking.

Algorithm Breakdown: DFS with Backtracking

Our solution will comprise two main parts:

1. An outer loop to iterate through every cell in the board. If a cell's character matches the first letter of our word, we initiate a DFS search from that point.
2. A recursive helper function (DFS) that attempts to find the rest of the word.

Let's detail the DFS helper function:

dfs(row, col, index, board, word)

• Base Case 1: Word Found

  • If index equals the length of word, it means we've successfully found all characters of the word in sequence. Return True.

• Base Case 2: Out of Bounds or Mismatch

  • If row or col are outside the board boundaries.
  • If the character board[row][col] does not match word[index].
  • If the cell (row, col) has already been visited (we'll mark visited cells).
  • In any of these cases, this path is invalid. Return False.

• Recursive Step:

  1. Mark Current Cell Visited: Temporarily change the character at board[row][col] to a distinct marker (e.g., '#', '*') to prevent reusing it in the current path.
  2. Explore Neighbors: Recursively call dfs for all four adjacent cells:
     • dfs(row + 1, col, index + 1, ...) (Down)
     • dfs(row - 1, col, index + 1, ...) (Up)
     • dfs(row, col + 1, index + 1, ...) (Right)
     • dfs(row, col - 1, index + 1, ...) (Left)
  3. Check Results: If any of these recursive calls return True, it means a path was found. Propagate True upwards.
  4. Backtrack (Unmark Cell): Crucially, restore the character board[row][col] to its original value. This allows other potential paths (started from different initial cells) to use this cell later. If we don't restore it, we might miss valid paths.
  5. Return False: If no path from this cell leads to the full word, return False.

The main function exist(board, word) will iterate (i, j) through the board. If board[i][j] == word[0], it calls dfs(i, j, 0, board, word). If any such call returns True, the word exists. If all initial calls fail, return False.

Python Code Implementation

Here's how you might implement this in Python:

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])

        # Define directions for movement (up, down, left, right)
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def dfs(r, c, k):
            # Base Case 1: Word Found
            if k == len(word):
                return True

            # Base Case 2: Out of Bounds or Mismatch
            # A visited cell will have its character temporarily changed to '#'
            # which won't match word[k], effectively handling 'already visited'.
            if not (0 <= r < rows and 0 <= c < cols and board[r][c] == word[k]):
                return False

            # Mark current cell as visited by changing its character
            # Store original character to restore later during backtracking
            original_char = board[r][c]
            board[r][c] = '#' # Use a special character to mark as visited

            # Explore neighbors
            found = False
            for dr, dc in directions:
                new_r, new_c = r + dr, c + dc
                if dfs(new_r, new_c, k + 1):
                    found = True
                    break # Optimization: If found, no need to check other directions

            # Backtrack: Restore the original character to the cell
            board[r][c] = original_char

            return found

        # Iterate through each cell to find the starting character of the word
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == word[0]:
                    if dfs(r, c, 0):
                        return True

        return False

Time and Space Complexity Analysis

• Time Complexity: O(M * N * 3^L)
  • M is the number of rows, N is the number of columns in the board.
  • L is the length of the word.
  • In the worst case, we might start a DFS from every cell (M * N possibilities).
  • For each DFS path, we explore up to L characters. From each character, we have 4 directions. However, since we cannot go back to the cell we just came from, there are effectively 3 choices for the next step after the first one. Hence, 3^L.
• Space Complexity: O(L)
  • This is primarily due to the recursion stack depth, which can go as deep as the length of the word.
  • We are modifying the board in-place to mark visited cells, so no additional visited set/array is explicitly used, saving space. If we used an auxiliary visited matrix, it would be O(M*N).

Tips for Similar Problems

This problem is a fantastic illustration of grid traversal with DFS and backtracking. Keep these principles in mind for similar challenges:

1. Identify the Search Space: Is it a grid, a tree, or a graph?
2. Define Base Cases: What conditions stop the recursion (success, failure)?
3. Define Recursive Step: How do you move from the current state to the next?
4. Manage State: How do you keep track of visited elements or accumulated results? (Here, modifying the board temporarily serves as the visited tracker).
5. Backtracking: If a path doesn't lead to a solution, always revert the changes made to the state to allow other paths to explore.

Practicing problems like "Number of Islands," "Surrounded Regions," or "Pacific Atlantic Water Flow" will further solidify your understanding of these techniques.

Conclusion

Solving LeetCode 79: Word Search isn't just about finding characters on a board; it's about mastering a powerful and widely applicable algorithmic pattern. By understanding and implementing DFS with backtracking, you gain a versatile tool for tackling complex search and exploration problems. Keep practicing, and you'll find these grid-based challenges increasingly intuitive!

Happy coding!

Further Reading & Resources

• LeetCode Problem 79: Word Search
• Depth-First Search (DFS) on Wikipedia
• Backtracking on Wikipedia
• LeetCode Official Website