We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Word Search

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be approached using Depth-First Search (DFS) to explore each path in the grid.
  • Backtracking is essential to revert the state when a path does not lead to a solution.
  • Word length and grid size constraints allow for a direct implementation of DFS without performance concerns.

Space and Time Complexity

Time Complexity: O(m * n * 4^L), where L is the length of the word. In the worst case, we explore all paths in the grid for every cell. Space Complexity: O(L) for the recursion stack, where L is the length of the word being searched.

Solution

The solution involves a Depth-First Search (DFS) algorithm to explore the grid. For each cell, we check if it matches the current character of the word. If it does, we mark it as visited and recursively check its neighbors (up, down, left, right). If we reach the end of the word, we return true. If we cannot find the word, we backtrack by unmarking the visited cell.

Code Solutions

def exist(board, word):
    if not board:
        return False

    rows, cols = len(board), len(board[0])
    
    def dfs(r, c, index):
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:
            return False
        
        # Mark the cell as visited by replacing the character
        temp, board[r][c] = board[r][c], '#'
        
        # Explore all possible 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
        board[r][c] = temp
        return found

    for i in range(rows):
        for j in range(cols):
            if dfs(i, j, 0):
                return True
    return False
← Back to All Questions