LeetCode: 79 Word Search

LeetCode 79: Word Search

https://leetcode.com/problems/word-search/

Problem Description:

Given an m x n board and a word, find if the 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:

Input: board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
], word = "ABCCED"
Output: True

The word "ABCCED" exists in the grid.

Solution Approach:

The problem can be solved using Depth-First Search (DFS) combined with backtracking. We will start from each cell in the grid and try to find the given word by exploring neighboring cells. If we find the word, we return True; otherwise, we backtrack and continue exploring other possible paths.

Key Steps:

1. DFS Function:

   • For each cell, check if it matches the current character of the word.
   • If it matches, recursively explore the neighboring cells (up, down, left, right).
   • Mark the cell as visited to avoid revisiting it within the same search path.
   • If the word is found, return True. Otherwise, unmark the cell and backtrack.

2. Start DFS from each cell in the grid:

   • If any DFS call returns True, the word is found in the grid.

Code Implementation (with detailed comments):

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # Get the number of rows and columns in the board
        rows, cols = len(board), len(board[0])

        # Helper function: DFS to search the word starting from (r, c)
        def dfs(r, c, index):
            # If the index matches the word length, the word is found
            if index == len(word):
                return True

            # Check boundaries and if the cell matches the current character
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:
                return False

            # Temporarily mark the cell as visited
            temp = board[r][c]
            board[r][c] = '#'

            # Explore all four directions (up, down, left, right)
            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)
            )

            # Restore the cell's original value (backtracking)
            board[r][c] = temp

            return found

        # Start DFS from each cell in the grid
        for i in range(rows):
            for j in range(cols):
                if dfs(i, j, 0):  # Start DFS if the character matches
                    return True

        return False

Code Explanation:

1. Initialization:

   • The function takes a 2D list board and a string word as input. We get the dimensions of the board using rows and cols.

2. DFS Function:

   • The helper function dfs(r, c, index) searches for the index-th character of the word starting from the cell (r, c).
   • If index equals the length of the word, it means the word is found, so return True.
   • If the cell is out of bounds or does not match the current character, return False.
   • Temporarily mark the cell as visited by changing its value to # and explore all four possible directions (up, down, left, right).
   • After exploring, restore the cell’s original value to allow further searches (backtracking).

3. Start DFS from each cell:

   • Iterate through each cell of the board. If the cell’s character matches the first character of the word, start a DFS from that cell.
   • If any DFS call returns True, it means the word exists in the grid.

Complexity Analysis:

• Time Complexity: O(m n 4^L), where m is the number of rows, n is the number of columns, and L is the length of the word. In the worst case, we might have to explore four directions at each step, leading to an exponential time complexity.
• Space Complexity: O(L), where L is the length of the word. This is the depth of the recursion stack.

Example Analysis:

For the input board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']] and word = "ABCCED":

1. Starting from the first cell (0, 0), we find the first character ‘A’ matches.
2. The DFS continues to the next cell and finds ‘B’, ‘C’, ‘C’, ‘E’, ‘D’ in sequence.
3. The word is found, and the function returns True.

Summary:

The solution uses DFS with backtracking to explore possible paths in the grid to find the given word. The backtracking ensures that each cell is used only once in each search path, and the search stops as soon as the word is found. This approach is effective for word search problems in grids, but it may become slow for large grids and long words due to its exponential time complexity.