Given a 2D board of characters and a list of words, find all words in the board.

Each word must 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 find_words(board: List[List[str]], words: List[str]) -> List[str]:
    """
    Find all words in the board.

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

    Returns:
    - List[str]: A list of words found in the board.
    """
    # Your code here

Example:

board = [
    ['o','a','a','n'],
    ['e','t','a','e'],
    ['i','h','k','r'],
    ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

print(find_words(board, words))  # Output: ["oath", "eat"]

Note:

  • You may assume that all inputs are consist of lowercase letters a-z.

Instructions:

  • Write the find_words 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 😊