 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://gitee.com/geektime-geekbang/algorithm-1

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

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

展开 

登录后留言

全部留言(26)

最新
精选

凤梨酥

不懂java为什么做不到相同的时间复杂度，感觉应该改改就可以啊

作者回复: Java也可以的。和语言的选择关系不太大。

2019-02-15



2

ANON.

代码在 leetcode 上跑不了

编辑回复: 把 Python 代码中的 xrange 换成 range 就可以了，或者你提交代码时编程语言选择 Python 而不是 Python3。因为在Python 3中，range()与xrange()合并为range( )。

2018-12-03



1

考拉出山

明明说着java版本更适合面时，却着重在python版本，每次看着python的语法糖，然后去用java实现相同的逻辑，都吐一口老血。ps: 个人觉得 java的实现比python的实现更有助于理解代码的过程和算法的本质

2020-03-07

2

15

十七年蝉

这道题算法的效率其实跟语言没什么关系，而是和实现有关系，老师找的Java解法确实不够好，可以看一下这个答案，细节处理的非常好，效率和Python的答案是一样的。 https://leetcode.com/problems/word-search-ii/discuss/59780/Java-15ms-Easiest-Solution-(100.00)

2019-07-27



5

熊之遥

这道题非常好，又考察了DFS，剪枝，又带有trie tre

2020-04-10



3

Abcd

C语言做这种题目就太酸爽了

2020-07-19



2

坤

第一种方法如果仅用DFS是不可以的吧，我是在LeetCode79 上用的DFS。还是要跟回溯结合的。至少我确实仅通过DFS没找到解决方案，还请覃老师指导一下。

2019-09-07

1

2

Aliliin

这道题好难。用 PHP写了好久，也不知道如何实现。

2019-11-21



1

Don

如果把END_OF_WORD flag 存成要找的word，就不用叠加cur word，可以找到直接存到答案里。

2018-12-22



1

Don

很清楚，同时进入trie的一层和board的下个一个字母，然后backtracking同时返回。java把trie子数组传一下也可以吧

2018-12-22



1

收起评论

	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