注意事项

本题中的 Python 代码使用的是 Python2.x 版本，如果使用 Python 3 ，需要将 xrange 改成 range。

在 Python 3 中，range() 与 xrange() 已合并为 range( )

完整代码如下：

from collections import defaultdict

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

END_OF_WORD = "#"

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

        if not board or not board[0]:
            return []
        if not words:
            return []

        self.result = set()

        root = defaultdict()

        for word in words:
            node = root
            for char in word:
                node = node.setdefault(char, defaultdict())
            node[END_OF_WORD] = END_OF_WORD

        self.m, self.n = len(board), len(board[0])

        for i in xrange(self.m):
            for j in xrange(self.n):
                if board[i][j] in root:
                    self._dfs(board, i, j, "", root)
        
        return list(self.result)


    def _dfs(self, board, i, j, cur_word, cur_dict):
        cur_word += board[i][j]
        cur_dict = cur_dict[board[i][j]]

        if END_OF_WORD in cur_dict:
            self.result.add(cur_word)
            
        tmp, board[i][j] = board[i][j], "@"
        for k in xrange(4):
            x, y = i + dx[k], j + dy[k]
            if 0 <= x < self.m and 0 <= y < self.n \
                and board[x][y] != "@" and board[x][y] in cur_dict:
                self._dfs(board, x, y, cur_word, cur_dict)
        board[i][j] = tmp
复制代码

课件下载地址

https://github.com/geektime-geekbang/algorithm-1

二维网格中的单词搜索问题

• 英文版：https://leetcode.com/problems/word-search-ii/
• 中文版：https://leetcode-cn.com/problems/word-search-ii/