8.14 - hard - 41

212. Word Search II

这道题分了两个层次，一个是要search word，第二个是要用Trie。基本上算是会做吧，但是达不到bug free的程度。

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        m = len(board)
        n = len(board[0])
        res = []
        words = set(words)
        root = TrieNode("")
        for word in words:
            node = root
            for c in word:
                if c not in node.children:
                    node.children[c] = TrieNode(c)
                node = node.children[c]
            node.stop = True
            node.word = word
        res = []
        for i in range(m):
            for j in range(n):
                visited = [[False for _ in range(n)] for _ in range(m)]
                self.find(board, visited, root, res, i, j)
        
        return res
    
    def find(self, board, visited, root, res, i, j):
        if root.stop:
            if root.word not in res:
                res.append(root.word)
        if 0 >i or i >= len(board) or 0 > j or j >= len(board[0]) or visited[i][j]:
            return
        if board[i][j] in root.children:
            visited[i][j] = True
            for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
                self.find(board, visited, root.children[board[i][j]], res, x, y)
            visited[i][j] = False
    
class TrieNode(object):
    def __init__(self, c):
        self.c = c
        self.stop = False
        self.word = None
        self.children = {}