LeetCode 79,这道走迷宫问题为什么不能用宽搜呢?

本文始发于个人公众号:TechFlow,原创不易,求个关注

今天是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 = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        def dfs(x, y, l):
            if l == len(word):
                return True
            for i in range(4):
                nx = x + fx[i][0]
                ny = y + fx[i][1]
                # 出界或者是走过的时候,跳过
                if nx < 0 or nx == n or ny < 0 or ny == m or visited[nx][ny]:
                    continue
                if board[nx][ny] == word[l]:
                    visited[nx][ny] = 1
                    if dfs(nx, ny, l+1):
                        return True
                    visited[nx][ny] = 0
            return False
                
        n = len(board)
        if n == 0:
            return False
        m = len(board[0])
        if m == 0:
            return False
        
        visited = [[0 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[0]:
                    visited = [[0 for _ in range(m)] for _ in range(n)]
                    visited[i][j] = 1
                    if dfs(i, j, 1):
                        return True
                    
        return False

总结

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

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

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

本文使用 mdnice 排版