当前播放: 38 | 面试题:二维网格中的单词搜索问题
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
课程目录
第一章:课程综述 (4讲)
01 | 合格程序员的第一步:算法与数据结构
免费
02 | 如何事半功倍地学习算法与数据结构
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算法题目练习
免费
第二章:理论讲解+面试题实战 (53讲)
05 | 理论讲解:数组&链表
免费
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
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 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
第三章:课程总结 (5讲)
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 结课测试&最后的一些经验分享
38 | 面试题:二维网格中的单词搜索问题

38 | 面试题:二维网格中的单词搜索问题

覃超
Sophon Tech创始人,前Facebook工程师,卡内基梅隆大学计算机硕士
全集23001
新人首单 ¥29.9 原价 ¥129
13
本节摘要

注意事项

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

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

展开
登录 后留言

精选留言(18)

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

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

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

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

    2018-12-03
    1
  • 熊之遥
    这道题非常好,又考察了DFS,剪枝,又带有trie tre
    2020-04-10
  • 张磊
    Trie字典数第一次听说,非常有用!
    2020-03-28
  • 考拉出山
    明明说着java版本更适合面时,却着重在python版本, 每次看着python的语法糖,然后去用java实现相同的逻辑,都吐一口老血。ps: 个人觉得 java的实现比python的实现更有助于理解代码的过程和算法的本质
    2020-03-07
  • Geek_8717fc
    看了很久不明白 为什么 要把x,y 恢复成未读的状态"visited [x][y] = false" 如果去掉 程序确实也不对,但是不知道什么道理
    2020-01-19
    1
  • Geek_8717fc
    老师 用DFS实现的方法能再讲得明白些吗?
    2020-01-18
  • lzh
    我还以为会说一下对大量重复字符的用例,如何进行剪枝呢....
    2020-01-15
  • 花花young
    看java 的感觉有个问题,比如字符串为 "tear" 和 "aet",搜索tear存在,进行aet搜索操作的时候岂不是会直接丢弃
    2020-01-15
  • Aliliin
    这道题好难。用 PHP写了好久,也不知道如何实现。
    2019-11-21
  • czh
    1.将矩阵按“规则”整理成“树”结构,并用dfs来暴力枚举
    2.使用trie进行改进
    2019-09-27
  • 第一种方法如果仅用DFS是不可以的吧,我是在LeetCode79 上用的DFS。 还是要跟回溯结合的。至少我确实仅通过DFS没找到解决方案,还请覃老师指导一下。
    2019-09-07
  • niubility
    这题我自己硬撸出来的,看了下跟老师的java代码基本差不多,就是参数命名,代码优雅度差了好多.这题能硬撸出来,是不是说明递归的编程能力还可以了?没看过老师教程之前,我铁定写不出.再次感谢老师.
    2019-06-06
  • Daven
    为什么不把那个board变成字典树,再去查那些单词?
    2019-05-19
  • 王磊
    Java实现里为什么同时调用了startWith()和search(),感觉只用search就行。他俩的实现和复杂度类似,前者没有比后者高效,所以如果是匹配的单词,相当于同时执行了两个方法,有一次浪费了;如果不是匹配的单词,也调用了startWith, 没有比search节约什么
    2019-05-05
    1
  • Don
    如果把END_OF_WORD flag 存成要找的word,就不用叠加cur word,可以找到直接存到答案里。
    2018-12-22
收起评论
看过的人还看
数据结构与算法之美

王争  前Google工程师

80讲 | 85869 人已学习

新人首单 ¥29.9 原价 ¥129
趣谈网络协议

刘超  网易研究院云计算技术部首席架构师

51讲 | 44817 人已学习

新人首单 ¥19.9 原价 ¥99
左耳听风

陈皓  网名“左耳朵耗子”,资深技术专家,骨灰级程序员

109讲 | 45576 人已学习

新人首单 ¥69.9 原价 ¥299
Java核心技术面试精讲

杨晓峰  前Oracle首席工程师

44讲 | 46474 人已学习

新人首单 ¥19.9 原价 ¥99