class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """

        class Trie(object):
            def __init__(self):
                self.children = {}

            def insert(self, word):
                if word[0] not in self.children:
                    self.children[word[0]] = Trie()
                l = len(word)
                if l == 1:
                    return
                self.children[word[0]].__insert(word, 1, l)

            def __insert(self, word, i, l):
                if word[i] not in self.children:
                    self.children[word[i]] = Trie()
                if l - i == 1:
                    return
                self.children[word[i]].__insert(word, i+1, l)

            def search(self, word):
                if word[0] not in self.children:
                    return False
                l = len(word)
                if l == 1:
                    return True
                return self.children[word[0]].__search(word, 1, l)

            def __search(self, word, i, l):
                if word[i] not in self.children:
                    return False
                if l - i == 1:
                    return True
                return self.children[word[i]].__search(word, i+1, l)

        from itertools import product
        from collections import namedtuple
        from copy import copy

        if type(board) is not list or len(board) == 0:
            return []
        if type(board[0]) is not list or len(board[0]) == 0:
            return []
        if type(words) is not list or len(words) == 0:
            return []

        m = len(board)
        n = len(board[0])

        trie = Trie()
        words = [ list(w) for w in words ]

        for word in words:
            trie.insert(word)

        Point = namedtuple('Point', ['x', 'y'])


        def crawl(_letters, c_point, _points, output):
            letters = copy(_letters)
            x = c_point.x
            y = c_point.y
            letters.append(board[x][y])

            points = _points.copy()
            points.add(c_point)

            if trie.search(letters):
                if letters in words:
                    w = ''.join(letters)
                    if w not in output:
                        output.append(w)



                # Make Points
                adjacent_points = []
                for p in [ Point(x-1,y), Point(x+1,y), Point(x,y-1), Point(x,y+1) ]:
                    if (p not in points and
                        m > p.x >= 0 and
                        n > p.y >= 0):
                            adjacent_points.append(p)

                for p in adjacent_points:
                    crawl(letters, p, points, output)

                return False

        output = []
        pointz = set()
        for i,j in product(range(m), range(n)):
            crawl([], Point(i,j), pointz, output)

        return output