algoadvance

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 those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum size of the board (m and n)?
    • What is the maximum length of the word?
  2. Character Repetition:
    • Can the word contain repeated characters?
  3. Output:
    • What should be returned if the word is found? Is it a simple boolean value?
  4. Edge Cases:
    • What should be returned if the board is empty or if the word is an empty string?
    • Do letters on the board contain both upper-case and lower-case characters, or only lower-case?

Strategy

We’ll use backtracking to explore all possible paths on the board from each cell to see if they lead to the given word. The key steps in our strategy:

  1. Iterate Through Each Cell: Start a DFS from each cell on the board.
  2. DFS with Backtracking:
    • Mark the current cell as visited.
    • Move to the adjacent cells (up, down, left, right) if they match the next character of the word.
    • If the word is found return True.
    • Backtrack (i.e., mark the cell as unvisited) if the current path does not lead to a solution.
  3. Boundary Check: Ensure that while accessing board cells, we are within the board’s bounds.

Time Complexity

The time complexity of this approach in the worst case is 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. This is because in the worst case, we might explore all 4 directions for each cell of the board.

Code

Here’s the Python code to solve this problem:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:
            return False
        
        self.rows = len(board)
        self.cols = len(board[0])
        self.word = word
        self.board = board

        for r in range(self.rows):
            for c in range(self.cols):
                if self._dfs(r, c, 0):
                    return True

        return False

    def _dfs(self, r, c, index):
        if index == len(self.word):
            return True
        if r < 0 or r >= self.rows or c < 0 or c >= self.cols or self.board[r][c] != self.word[index]:
            return False
        
        # Temporary mark the cell as visited
        temp = self.board[r][c]
        self.board[r][c] = '#'

        # Explore all possible directions
        for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            if self._dfs(r + dr, c + dc, index + 1):
                return True

        # Backtrack and unmark the cell
        self.board[r][c] = temp
        
        return False

Explanation

  1. Initialization: We check if the board is empty. We initialize the dimensions (rows and cols) and store the word and the board.
  2. Starting DFS: We start DFS from each cell (r, c) in the board.
  3. DFS Function (_dfs):
    • Base Case: If the current index matches the length of the word, it means the word has been found.
    • Boundary Checks: Ensure we are within the bounds of the board and the current cell matches the character in the word.
    • Marking the Cell: Temporarily mark the current cell as visited.
    • Explore Directions: Recursively visit all 4 adjacent cells.
    • Backtrack: If no solution is found along the path, unmark the cell to restore it for other possible paths.

This code efficiently explores all potential ways to form the word while ensuring that no cell is reused more than once in a single path.

Try our interview co-pilot at AlgoAdvance.com