社区首页 >专栏 >LeetCode 79，明明是走迷宫问题，为什么不能用宽搜呢？

LeetCode 79，明明是走迷宫问题，为什么不能用宽搜呢？

TechFlow-承志

发布于 2020-06-24 02:20:01

95300

代码可运行

文章被收录于专栏：TechFlowTechFlow

运行总次数：0

代码可运行

今天是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