Question

Code

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

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


class Solution(object):
    def findWords(self, board, words):
        root = TrieNode()

        for w in words:
            root.addWord(w)

        res, visited = set(), set()

        row, col = len(board), len(board[0])

        def dfs(r, c, node, word):
            if r < 0 or r >= row or c < 0 or c >= col or (r, c) in visited or board[r][c] not in node.children:
                return

            visited.add((r, c))
            node = node.children[board[r][c]]
            word += board[r][c]

            if node.isWord:
                res.add(word)
                node.isWord = False

            dfs(r + 1, c, node, word)
            dfs(r - 1, c, node, word)
            dfs(r, c + 1, node, word)
            dfs(r, c - 1, node, word)

            visited.remove((r, c))

        for i in range(row):
            for j in range(col):
                dfs(i, j, root, "")

        return list(res)