class Solution:
    """
    @param board: A list of lists of character
    @param words: A list of string
    @return: A list of string
    """

    def wordSearchII(self, board, words):
        # write your code here
        if not words or not board:
            return []

        self.res = set()
        for word in words:
            if self.search(board, word):
                self.res.add(word)
        return list(self.res)

    def search(self, board, word):
        m, n = len(board), len(board[0])

        visited = [[False] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if self.dfs(board, word, i, j, 0, visited):
                    return True
        return False

    def dfs(self, board, word, i, j, index, visited):
        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]

        if board[i][j] != word[index]:
            return False

        if index == len(word) - 1:
            print(index)
            return True

        visited[i][j] = True
        for k in range(4):
            x, y = i + dirs[k][0], j + dirs[k][1]
            if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]):
                continue
            if self.dfs(board, word, x, y, index + 1, visited):
                return True
            visited[i][j] = False
        return False

if __name__ == "__main__":
    sol = Solution()
    # board = [['d','o','a','f'],['a','g','a','i'],['d','c','a','n']]
    # words = ["dog","dad","dgdg","can","again"]
    # r = sol.search(board, "dog")
    # print(r)
    # res = sol.wordSearchII(board, words)
    # print(res)
    board = ["b","a","b","b","a"]
    words = ["babbab"]
    r = sol.search(board, "babbab")
    print(r)

    r = sol.wordSearchII(board, words)
    print(r)