Word Search II

还是Trie树和DFS结合的应用，不过是二维的DFS了，这里除了一般二维搜索需要注意的边界问题，查重问题，还要注意trie树结点和递归层的一致性，这里非常容易搞错两个结构差了一层，最后还要注意，很有可能从不同地点都能找到同一个词，我们无法通过搜索的减枝去掉这个重复（真的没办法？)*，但是我们可以利用set收集结果最后变成list

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        n = len(board)
        if not n:
            return []

        m = len(board[0])
        if not m:
            return []

        trieNode = self.buildTrie(words)
        result = set()
        ref = [[0] * m for _ in xrange(n)]
        for i in xrange(n):
            for j in xrange(m):
                if board[i][j] in trieNode:
                    self.helper(i, j, n, m, board, ref, trieNode[board[i][j]], result, board[i][j])

        return list(result)

    def helper(self, row, col, n, m, board, ref, trieNode, result, tmp):
        if '#' in trieNode:
            result.add(tmp[:])

        ref[row][col] = 1
        for i, j in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
            curRow, curCol = row + i, col + j
            if 0 <= curRow < n and 0 <= curCol < m and not ref[curRow][curCol] and board[curRow][curCol] in trieNode:
                self.helper(curRow, curCol, n, m, board, ref, trieNode[board[curRow][curCol]], result, tmp + board[curRow][curCol])


        ref[row][col] = 0

    def buildTrie(self, words):
        result = {}
        for word in words:
            cur = result
            for char in word:
                cur.setdefault(char, {})
                cur = cur[char]
            cur['#'] = {}
        return result

这里可以不需要ref矩阵来查重，而通过修改一个原本矩阵里不可能存在的值来查重