from typing import (
    List,
)

DIRECTIONS = [
    (1, 0),
    (0, 1),
    (-1, 0),
    (0, -1) 
]

class TrieNode():
    def __init__(self):
        self.children = {}
        self.isWord = False

class Trie():
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.isWord = True

    def search(self, word):
        node = self.root
        for c in word:
            if c in node.children:
                node = node.children[c]
            else:
                return False
        return node.isWord

    def startswith(self, prefix):
        # print(prefix)
        node = self.root
        for c in prefix:
            if c in node.children:
                node = node.children[c]
            else:
                return False
        return True

class Solution:
    """
    @param board: A list of lists of character
    @param words: A list of string
    @return: A list of string
    """
    def word_search_i_i(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board:
            return []

        # self.prefix_set = self.make_prefix_set(words)
        self.trie = Trie()
        for word in words:
            self.trie.insert(word)
        self.ans = []


        for x in range(len(board)):
            for y in range(len(board[0])):
                self.dfs(board, words, x, y, set(), "")

        return self.ans        


    def dfs(self, board, words, x, y, visited, prefix):
        # print(prefix)
        # end of recursion
        if not words: # all finished
            return

        if prefix in words:
            self.ans.append(prefix[:])
            words.remove(prefix[:]) # prevent duplicate

        # if prefix != "" and prefix not in self.prefix_set:
        if prefix != "" and not self.trie.startswith(prefix):
            return 


        # define and split
        if not self.is_in_bound(x, y, board):
            return 

        if (x,y) in visited:
            return 

        visited.add((x, y))
        for dx, dy in DIRECTIONS:
            self.dfs(board, words, x+dx, y+dy, visited, prefix+board[x][y])
        visited.remove((x, y)) # backtracking


    def is_in_bound(self, x, y, board):
        m, n = len(board), len(board[0])
        return 0 <= x < m and 0 <= y < n

#     def make_prefix_set(self, words):
#         prefix_set = set()
#         for word in words:
#             for i in range(len(word)):
#                 prefix_set.add(word[:i+1])

#         return prefix_set