Given a 2D board of letters and a word, determine if the 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 in a word.

Function Signature:

from typing import List

def word_search(board: List[List[str]], word: str) -> bool:
    """
    Determine if the word exists in the 2D board of letters.

    Parameters:
    - board: A 2D list of characters representing the board of letters.
    - word: The word to search for.

    Returns:
    - bool: True if the word exists in the board, False otherwise.
    """
    # Your code here

Example:

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

Instructions:

  • Write the word_search function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊