题目难度: 中等

原题链接

今天继续更新剑指 offer 系列, 这道题用到了经典的图算法, 而且时间和空间上都有一些可以优化的地方, 质量不错 ​

老样子晚上 6 点 45 分准时跟大家见面, 大家在我的公众号"每日精选算法题"中的聊天框中回复 offer 就能看到剑指 offer 系列当前连载的所有文章了

大家有什么想法建议和反馈的话欢迎随时交流, 包括但不限于公众号聊天框/知乎私信评论等等~

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的 3×4 的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200

题目样例

示例 1

输入

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

输出

true

示例 2

输入

board = [["a","b"],["c","d"]], word = "abcd"

输出

false

题目思考

  1. 有没有什么直观思路?
  2. 如何判断某个字符是否已经被访问?

解决方案

思路

分析

  • 分析题意, 这道题需要求目标字符串的路径, 且只要找到一个满足条件的即可, 所以特别适合用 DFS 来做. 因为 DFS 比较方便记录每条遍历过的路径, 正好可以用在这里
  • 所以我们可以从任意一个字符开始, 依次比较它和目标字符串当前下标对应的字符, 如果相等的话, 就可以继续向四周遍历, 同时字符串下标加 1
  • 直到字符串下标达到字符串长度, 这个时候就说明我们找到了一个满足要求的路径, 直接返回 true 即可
  • 而如果遍历过程中某个字符并不匹配, 我们就不要继续往下遍历下去了, 因为肯定不满足条件
  • 另外注意需要判断某个字符是否已经访问过, 所以我们需要额外定义一个 visit 集合, 用于存储已经访问的元素行列下标: 在递归调用某个字符之前将其加入行列下标加入集合中, 调用结束后还要将其移除, 恢复现场, 避免这个下标之后在其他路径中不能被用到

实现

  • 经典的 DFS, 需要额外 visit 集合, 以及当前目标字符串的下标
  • 依次遍历矩阵的每个字符, 如果当前字符与目标字符串的开头相同, 就以它为起点进行 DFS, 如果发现一条满足条件的路径就直接返回 true, 否则继续遍历
  • 优化
    • visit 集合可以利用对原始矩阵的字符替换为 None 或其他不存在的字符代替, 而恢复时再将其替换回来即可, 这样可以节省一些空间
    • 如果某个方向已经找到路径了, 就没必要继续遍历下去, 直接返回即可, 这样剪枝可以节省一些时间
  • 下面代码对各个步骤都有详细解释, 特别是时间和空间优化的部分, 方便大家理解

复杂度

  • 时间复杂度 O((3^L)*RC)
    • 假设 L 是目标字符串长度, RC 是矩阵行和列数
    • 每次递归调用都需要考虑 3 个方向(不可能返回上一个字符, 因为它已经被访问了, 不会重复被访问, 所以是 3 个方向), 最多要调用到长度为 L 的路径, 这部分就是 O(3^L)
    • 而一共需要遍历 RC 个字符, 这部分是O(RC)
    • 所以时间复杂度是O((3^L)*RC)
  • 空间复杂度 O(L)
    • 优化掉 visit 集合后, 只需要考虑递归的栈的空间, 而递归深度最大为 L(当路径长度超过 L 后没必要继续下去), 所以空间复杂度就是O(L)

代码

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # DFS + 回溯
        # 针对每一个首字符, 找所有可能的字符串, 剪枝
        rows, cols = len(board), len(board[0])

        def dfs(r, c, i):
            # i表示当前的目标字符串下标
            if i == len(word):
                # 如果已经遍历完整个目标字符串, 则说明找到一条有效路径, 直接返回True
                return True
            # 4个方向遍历 (注意实际只会有3个方向继续下去, 因为上一个节点已经被访问过, 不会再访问它)
            for (rr, cc) in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= rr < rows and 0 <= cc < cols and board[rr][cc] == word[i]:
                    # 优化1: 将visit集合优化为直接标记原矩阵, 节省空间
                    # 注意上面不需要再判断board[rr][cc]是否是None (是否被访问过), 因为如果是None的话肯定不可能等于word[i]
                    cur, board[rr][cc] = board[rr][cc], None
                    if dfs(rr, cc, i + 1):
                        # 优化2: 剪枝, 找到一条路径直接返回True, 节省时间
                        return True
                    board[rr][cc] = cur
            return False

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == word[0]:
                    # 只有当前字符与目标字符串开头相同时才开始DFS, 其他字符开头就不相同
                    # 注意需要先将起始字符标记成访问过, 避免重复再访问它
                    cur, board[r][c] = board[r][c], None
                    if dfs(r, c, 1):
                        return True
                    board[r][c] = cur
        # 没找到有效路径, 返回False
        return False

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊

每日精选算法题 - 微信扫一扫关注我