Word Search medium

Problem Statement

Given an m x n board and a word word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

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

Steps

  1. Depth-First Search (DFS): We'll employ a recursive DFS approach to explore all possible paths in the board.

  2. Base Cases:

    • If the word is empty, we've found it, so return True.
    • If we're out of bounds or the current cell doesn't match the expected letter, return False.

  3. Recursive Step:

    • Mark the current cell as visited (to avoid cycles).
    • Recursively explore the four adjacent cells (up, down, left, right).
    • If any recursive call returns True, we've found the word, so return True.
    • Backtrack: Unmark the current cell as visited (to explore other paths).
    • If none of the recursive calls find the word, return False.

Explanation

The algorithm systematically explores all possible paths within the board using DFS. By marking cells as visited and backtracking, it efficiently avoids revisiting the same cell in a path and ensures that each path is explored completely before moving on to another. The base cases handle the situations where the word is found or when a path becomes invalid.

Code

def exist(board, word):
    """
    Finds if a word exists in a given board using DFS.

    Args:
        board: A list of lists representing the board (characters).
        word: The word to search for (string).

    Returns:
        True if the word exists, False otherwise.
    """
    rows, cols = len(board), len(board[0])

    def dfs(row, col, index):
        if index == len(word):  # Base case: Word found
            return True
        if row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] != word[index]:
            return False  # Base case: Out of bounds or mismatch

        temp = board[row][col]  # Store the original character
        board[row][col] = '#'  # Mark as visited

        # Explore adjacent cells
        found = (dfs(row + 1, col, index + 1) or
                 dfs(row - 1, col, index + 1) or
                 dfs(row, col + 1, index + 1) or
                 dfs(row, col - 1, index + 1))

        board[row][col] = temp  # Backtrack: Restore the original character

        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Complexity

  • Time Complexity: O(M * N * 4L), where M and N are the dimensions of the board, and L is the length of the word. In the worst case, we might explore all possible paths.
  • Space Complexity: O(L) due to the recursive call stack (depth of recursion is at most L). The space used for marking visited cells is also O(L) in the worst-case (though it's technically O(M*N) if we used a separate visited matrix).