绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
LeetCode 79,明明是走迷宫问题,为什么不能用宽搜呢?
2020-06-23 14:45:32

今天是LeetCode专题第48篇文章,我们一起来看看LeetCode当中的第79题,搜索单词(Word Search)。

这一题官方给的难度是Medium,通过率是34.5%,点赞3488,反对170。单从这份数据上来看,这题的质量很高,并且难度比之前的题目稍稍大一些。我个人觉得通过率是比官方给的题目难得更有参考意义的指标,10%到20%可以认为是较难的题,30%左右是偏难的题。50%是偏易题,所以如果看到某题标着Hard,但是通过率有50%,要么说明题目很水,要么说明数据很水,总有一点很水。


题意

废话不多说,我们来看题意:

这题的题面挺有意思,给定一个二维的字符型数组,以及一个字符串,要求我们来判断能否在二维数组当中找到一条路径,使得这条路径上的字符连成的字符串和给定的字符串相等?

样例

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED"return true.
Given word = "SEE"return true.
Given word = "ABCB"return false.

比如个字符串ABCCED,我们可以在数组当中找到这样一条路径:


题解

不知道大家看到题面和这个样例有什么样的感觉,如果你刷过许多题,经常思考的话,我想应该不难发现,这道题的本质其实和走迷宫问题是一样的。

我们拿到的这个二维的字符型数组就是一个迷宫, 我们是要在这个迷宫当中找一条“出路”。不过我们的目的不是找到终点,而是找到一条符合题意的路径。在走迷宫问题当中,迷宫中不是每一个点都可以走的,同样在当前问题当中,也不是每一个点都符合字符串的要求的。这两个问题虽然题面看起来大相径庭,但是核心的本质是一样的。

我们来回忆一下,走迷宫问题应该怎么解决?

这个答案应该已经非常确定了,当然是搜索算法。我们需要搜索解可能存在的空间去寻找存在的解,也就是说我们面临的是一个解是否存在的问题,要么找到解,要么遍历完所有的可能性发现解不存在。确定了是搜索算法之后,剩下的就简单了,我们只有两个选项,深度优先或者是广度优先。

理论上来说,一般判断解的存在性问题,我们使用广度优先搜索更多,因为一般来说它可以更快地找到解。但是本题当中有一个小问题是,广度优先搜索需要在队列当中存储中间状态,需要记录地图上行走过的信息,每有一个状态就需要存储一份地图信息,这会带来比较大的内存开销,同样存储的过程也会带来计算开销,在这道题当中,这是不可以接受的。拷贝状态带来的空间消耗还是小事,关键是拷贝带来的时间开销,就足够让这题超时了。所以我们别无选择,只能深度优先。

明确了算法之后,只剩下了后一个问题,在这个走迷宫问题当中,我们怎么找到迷宫的入口呢?因为题目当中并没有规定我们起始点的位置,这也不难解决,我们遍历二维的字符数组,和字符串开头相匹配的位置都可以作为迷宫的入口。

后,我们来看代码,并没有什么技术含量,只是简单的回溯法而已。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        fx = [[1], [-1], [1], [-1]]
        def dfs(x, y, l):
            if l == len(word):
                return True
            for i in range(4):
                nx = x + fx[i][]
                ny = y + fx[i][1]
                # 出界或者是走过的时候,跳过
                if nx  or nx == n or ny <  or ny == m or visited[nx][ny]:
                    continue
                if board[nx][ny] == word[l]:
                    visited[nx][ny] = 1
                    if dfs(nxnyl+1):
                        return True
                    visited[nx][ny] = 
            return False
                
        n = len(board)
        if n == :
            return False
        m = len(board[])
        if m == :
            return False
        
        visited = [[ for i in range(m)] for j in range(n)]
        
        for i in range(n):
            for j in range(m):
                # 找到合法的起点
                if board[i][j] == word[]:
                    visited = [[ for _ in range(m)] for _ in range(n)]
                    visited[i][j] = 1
                    if dfs(ij1):
                        return True
                    
        return False


总结

如果能够想通回溯法,并且对于回溯法的实现足够熟悉,那么这题的难度是不大的。实际上至今为止,我们一路刷来,已经做了好几道回溯法的问题了,我想对你们来说,回溯法的问题应该已经小菜一碟了。

相比于回溯法来说,我觉得更重要的是我们能够通过分析想清楚,为什么广度优先搜索不行,底层核心的本质原因是什么。这个思考的过程往往比后的结论来得重要。

如果喜欢本文,可以的话,请点个关注,给我一点鼓励,也方便获取更多文章。


分享好友

分享这个小栈给你的朋友们,一起进步吧。

TechFlow
创建时间:2020-03-19 11:13:43
机器学习、算法与数据结构、大数据相关和Python。 从纯基础开始的算法领域入门以及进阶内容。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • chengycz
    栈主

小栈成员

查看更多
  • 兔子爱喝红茶
  • 小雨滴
  • ittttliu
  • 栈栈
戳我,来吐槽~