下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 38 | 面试题:二维网格中的单词搜索问题
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18804
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
12 | 面试题:返回滑动窗口中的...
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二...
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索...
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时...
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最...
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方...
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词...
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&...
42 | 面试题:N皇后问题的另一...
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径...
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友...
54 | 面试题:岛屿的个数&朋友...
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享
本节摘要

注意事项

本题中的 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

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

展开

精选留言(11)

  • 2019-07-27
    这道题算法的效率其实跟语言没什么关系,而是和实现有关系,老师找的Java解法确实不够好,可以看一下这个答案,细节处理的非常好,效率和Python的答案是一样的。
     https://leetcode.com/problems/word-search-ii/discuss/59780/Java-15ms-Easiest-Solution-(100.00)
    1
  • 2019-02-15
    不懂java为什么做不到相同的时间复杂度,感觉应该改改就可以啊

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

    1
  • 2018-12-22
    很清楚,同时进入trie的一层和board的下个一个字母,然后backtracking同时返回。java把trie子数组传一下也可以吧
    1
  • 2018-12-03
    代码在 leetcode 上跑不了

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

    1
  • 2019-11-21
    这道题好难。用 PHP写了好久,也不知道如何实现。
  • 2019-09-27
    1.将矩阵按“规则”整理成“树”结构,并用dfs来暴力枚举
    2.使用trie进行改进
  • 2019-09-07
    第一种方法如果仅用DFS是不可以的吧,我是在LeetCode79 上用的DFS。 还是要跟回溯结合的。至少我确实仅通过DFS没找到解决方案,还请覃老师指导一下。
  • 2019-06-06
    这题我自己硬撸出来的,看了下跟老师的java代码基本差不多,就是参数命名,代码优雅度差了好多.这题能硬撸出来,是不是说明递归的编程能力还可以了?没看过老师教程之前,我铁定写不出.再次感谢老师.
  • 2019-05-19
    为什么不把那个board变成字典树,再去查那些单词?
  • 2019-05-05
    Java实现里为什么同时调用了startWith()和search(),感觉只用search就行。他俩的实现和复杂度类似,前者没有比后者高效,所以如果是匹配的单词,相当于同时执行了两个方法,有一次浪费了;如果不是匹配的单词,也调用了startWith, 没有比search节约什么
    1
  • 2018-12-22
    如果把END_OF_WORD flag 存成要找的word,就不用叠加cur word,可以找到直接存到答案里。