Word Search

Problem Statement

Given a 2-D grid of characters board and a string word, return true if the word is present in the grid, otherwise return false.

For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Example 1:

Input:
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "CAT"

Output: True

Example 2:

Input:
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "BAT"

Output: False

Constraints:

• 1 <= board.length, board[i].length <= 5
• 1 <= word.length <= 10
• board and word consists of only lowercase and uppercase English letters.

You should aim for a solution with O(m * (4^n)) time and O(n) space, where m is the number of cells in the given board and n is the size of the given word.

Recommended Time and Space Complexity

You should aim for a solution with O(m * (4^n)) time and O(n) space, where m is the number of cells in the given board and n is the size of the given word.

Hint 1

As we can start at any cell on the board, we can explore all paths from that cell. Can you think of an algorithm to do so? Also, you should consider a way to avoid visiting a cell that has already been visited in the current path.

Hint 2

We can use a hash set to avoid revisiting a cell in the current path by inserting the (row, col) of the visiting cell into the hash set and exploring all paths (four directions, as we can move to four neighboring cells) from that cell. Can you think of the base condition for this recursive path? Maybe you should consider the board boundaries, and also, we can extend a path if the character at the cell matches the character in the word.

Hint 3

We can use backtracking, starting from each cell on the board with coordinates (row, col) and index i for the given word. We return false if (row, col) is out of bounds or if board[row][col] != word[i]. When i reaches the end of the word, we return true, indicating a valid path. At each step, we add (row, col) to a hash set to avoid revisiting cells. After exploring the four possible directions, we backtrack and remove (row, col) from the hash set.

Solution

Backtracking (Hash Set)

def exist(board: List[List[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    path = set()

    def dfs(r, c, i):
        if i == len(word):
            return True

        if (min(r, c) < 0 or
            r >= rows or c >= cols or
            word[i] != board[r][c] or
            (r, c) in path):
            return False

        path.add((r, c))
        res = (dfs(r + 1, c, i + 1) or
               dfs(r - 1, c, i + 1) or
               dfs(r, c + 1, i + 1) or
               dfs(r, c - 1, i + 1))
        path.remove((r, c))
        return res

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

Time complexity: O(m * 4 ^ n) Space complexity: O(n)