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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Word Search

Number: 79

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg, Uber, Microsoft, TikTok, Google, Meta, Karat, Salesforce, Netflix, Oracle, PayPal, Faire, Atlassian, Goldman Sachs, Walmart Labs, Apple, Samsung, Zoho, Epic Systems, Grammarly, Wix, Snap, Capital One, Adobe, Cisco, Citadel, Visa

Problem Description

Given an m x n grid of characters (board) and a string (word), determine if the word exists in the grid. The word must be constructed from letters of sequentially adjacent cells (horizontally or vertically) and a cell cannot be used more than once.

Key Insights

  • Use Depth-First Search (DFS) to explore each cell in the board as a potential starting point.
  • Employ backtracking to mark cells as visited when exploring a path and revert them back when backtracking.
  • Check boundary conditions and ensure the current cell’s character matches the corresponding character in the word.
  • Given the small grid and word sizes, a recursive solution is both feasible and straightforward.
  • Search pruning can be applied by stopping a DFS branch as soon as the current path does not match the prefix of the target word.

Space and Time Complexity

Time Complexity: O(m * n * 3^L), where L is the length of the word (each DFS may branch to at most 3 further cells, excluding the coming cell). Space Complexity: O(L) due to recursion call stack (where L is the word length).

Solution

The solution uses DFS with backtracking to traverse the grid. For each cell, we:

  1. Check if the cell matches the first character of the word.
  2. Recursively explore the adjacent cells (up, down, left, right) while marking the current cell as visited.
  3. If the path does not lead to a complete match, backtrack by resetting the visited cell.
  4. The DFS stops if all characters in the word have been found in sequence.

The algorithm leverages in-place modifications (or an auxiliary visited array) to avoid revisiting cells while exploring a candidate path.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java with explanatory comments.

# Define the function to solve the Word Search problem.
def exist(board, word):
    # Get dimensions of the board.
    rows, cols = len(board), len(board[0])
    
    # Helper function for DFS search.
    def dfs(r, c, index):
        # If the entire word is found, return True.
        if index == len(word):
            return True
        
        # Check boundaries and if current cell already used or not matching.
        if r < 0 or c < 0 or r >= rows 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.
        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))
        
        # Backtrack: restore the original cell value.
        board[r][c] = temp
        return found

    # Initiate DFS from each cell in the grid.
    for i in range(rows):
        for j in range(cols):
            if dfs(i, j, 0):
                return True
    return False

# Example test case
if __name__ == "__main__":
    board = [
        ["A", "B", "C", "E"],
        ["S", "F", "C", "S"],
        ["A", "D", "E", "E"]
    ]
    word = "ABCCED"
    print(exist(board, word))  # Expected output: True
← Back to All Questions