# Question: Alphabet Word Search II
# 
# You are given an M x N board of characters and a list of strings called dictionary. Find all unique words in the dictionary that can be found in the board.
# 
# A word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally, vertically, or diagonally neighboring. The same letter cell may not be used more than once in a single word.
# 
# Implement a function findWords(board, dictionary) that returns a list of all unique words found.
# 
# Example:
# 
# Board:
# 
# [['o', 'a', 'b', 'n'],
#  ['o', 't', 'a', 'e'],
#  ['a', 'h', 'k', 'r'],
#  ['a', 'f', 'l', 'v']]
# 
 
# Dictionary: ["oath", "pea", "eat", "rain", "hobo", "oats"]
# 
# Expected Output: ["oath", "eat", "hobo", "oats"]
# 
# Constraints & Requirements:
 
# The search should be optimized for large dictionaries.
 
# Clearly explain your chosen data structure and algorithm for prefix matching and path finding.

from collections import deque
from os import wait
from typing import List


board = [
 ['o', 'a', 'b', 'n'],
 ['o', 't', 'a', 'e'],
 ['a', 'h', 'k', 'r'],
 ['a', 'f', 'l', 'v']
]
dictionary = ["oath", "pea", "eat", "rain", "hobo", "oats"]
directions = [
    (0, 1),
    (0, -1),
    (1, 0),
    (-1, 0),
    (1, 1),
    (-1, -1),
    (1, -1),
    (-1, 1),
]

def find_words(board: List[List[str]], dictionary: List[str]):
    tree = {}
    for row in range(len(board)):
        for col in range(len(board)):
            dfs(row, col, tree)

    ans = []
    for word in dictionary:
        curr = tree
        possible = True
        for letter in word:
            if letter not in curr:
                possible = False
                break
            curr = curr[letter]
        if possible:
            ans.append(word)

    return ans


def dfs(row, col, tree):
    if not (row >= 0 and row < len(board)\
            and col >= 0 and col < len(board[0])):
        return {}

    if board[row][col] == "#":
        return {}

    letter = board[row][col]
    children = {}
    board[row][col] = "#"

    for direction in directions:
        new_row, new_col = row + direction[0], col + direction[1]
        child_node = dfs(new_row, new_col, tree[letter])
        if child_node:
            children.update(child_node)

    board[row][col] = letter

    return { letter: children }

print(find_words(board, dictionary))