Intuition:

To solve this problem, we can use a depth-first search (DFS) algorithm. We’ll start by iterating through each cell in the board. For each cell, we’ll check if the current character matches the first character of the word. If it does, we’ll initiate a DFS search from that cell to find if the word can be constructed by traversing adjacent cells recursively. During the DFS search, we’ll mark visited cells to avoid revisiting them. If we find the word, we’ll return True; otherwise, we’ll continue searching. If no match is found after iterating through all cells, we’ll return False.

Solution:

from typing import List

def word_search(board: List[List[str]], word: str) -> bool:
    def dfs(i: int, j: int, k: int) -> bool:
        # Base case: If the index k reaches the end of the word, it means we found the word
        if k == len(word):
            return True
        # Check boundaries and whether the current cell matches the word character
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
            return False
        # Temporarily mark the cell as visited
        temp = board[i][j]
        board[i][j] = '#'
        # DFS search in adjacent cells
        found = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
        # Restore the cell's original value after DFS search
        board[i][j] = temp
        return found

    # Iterate through each cell in the board
    for i in range(len(board)):
        for j in range(len(board[0])):
            # Start DFS search from each cell
            if dfs(i, j, 0):
                return True
    return False

# Test cases
board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
print(word_search(board, "ABCCED"))  # Output: True
print(word_search(board, "SEE"))     # Output: True
print(word_search(board, "ABCB"))    # Output: False

board = []
print(word_search(board, "E"))  # Output: False

board = [['A']]
print(word_search(board, "E"))  # Output: False
print(word_search(board, "A"))  # Output: True

Time Complexity:

  • Let n be the number of cells in the board, m be the length of the longest word.
  • In the worst case, we perform DFS search from each cell of the board, resulting in a time complexity of O(n).
  • Each DFS traversal starting from a cell has a worst-case time complexity of O(4^m). This is because, at each step of the DFS, we have up to 4 directions to explore (up, down, left, right), and we recurse for each valid direction. The maximum depth of recursion is determined by the length of the longest word.
  • Overall, the time complexity is O(n * 4^m).

Space Complexity:

  • The space complexity is O(m) for the recursive call stack, where m is the length of the longest word.
  • Additionally, we use O(1) extra space for variables and function calls.
  • Therefore, the overall space complexity is O(m).