note:典型的迷宫找路的问题,一般都是使用基于dfs+剪枝的回溯方法。
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如,在下面的 3×4 的矩阵中包含单词 “ABCCED”(单词中的字母已标出)。
示例 1:
1 | 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" |
示例 2:
1 | 输入:board = [["a","b"],["c","d"]], word = "abcd" |
提示:
- 1 <= board.length <= 200
- 1 <= board[i].length <= 200
- board 和 word 仅由大小写英文字母组成
方法:回溯法
思路
很显然,对于这种矩阵搜索、迷宫找路径的题目,一般必然是使用深度优先搜索+剪枝来进行解决的。
在这道题中,我们首先可以想到,我们只需要以矩阵中每个元素作为起始元素,判断以这个元素开始是否能够找到word。
然后开始设想如何以某个元素作为起始进行寻找。首先考虑的深度优先搜索,就会发现搜索过的地方会重复搜索,浪费大量时间,甚至递归无法停止,所以我们一定要标记好访问过的地方,一但访问了,就要做好标记,而一但发现此路不通,进行回溯的时候,就要把标记改回来。这就是剪枝的部分。
考虑dfs的流程是如何的。一般dfs肯定是使用递归写方便,递归的终止条件非常重要,很显而易见的终止条件有以下几个
- 超出矩阵边界。返回false。
- 访问到的元素和要找的字符串中对应的元素不相同。返回false
- 字符串所有字符都已经找遍,全部对应上了。完全匹配。返回true
那递归要完成什么呢?
- 标记已经访问的元素
- 向上下左右四个方向进行探索,看往下走是否满足字符串的匹配(开启下层递归),四个方向只要有一个方向可以满足就满足情况
- 恢复已经访问的标记。
为什么之后要恢复已经访问的标记呢?这是因为走到这一步时,下层递归都已经完成,本层工作也已经做完,将要返回到上层递归,而所有的本层递归所做的标记,对于上层递归而言是无意义的。甚至会干扰的上层递归的访问。所以要恢复所做的标记。也就是说,标记仅影响本层以下的所有递归操作。
标记的行为可以有很多实现,比如重新建立一个等大的矩阵来记录。但是为了节省空间,我们不妨就在原数组进行更改,更改为一个不可能在字符串中出现的元素就好,然后在递归结束之后,再将元素改过来就可以了。
代码
1 | class Solution { |
复杂度分析
M,N 分别为矩阵行列大小, KK 为字符串 word 长度。
- 时间复杂度 $O(3^KMN)$: 最差情况下,需要遍历矩阵中长度为$ K $字符串的所有方案,时间复杂度为 $O(3^K)$;矩阵中共有$ MN$个起点,时间复杂度为 $O(MN)$ 。
方案数计算: 设字符串长度为 $KK$ ,搜索中每个字符有上、下、左、右四个方向可以选择,舍弃回头(上个字符)的方向,剩下 3 种选择,因此方案数的复杂度为 $O(3^K)$ 。
空间复杂度$ O(K)$ : 搜索过程中的递归深度不超过 $K$ ,因此系统因函数调用累计使用的栈空间占用$ O(K)$ (因为函数返回后,系统调用的栈空间会释放)。最坏情况下 $K = MN$ ,递归深度为 $MN$ ,此时系统栈使用$ O(MN)$ 的额外空间。
(复杂度分析参考题解)
原文链接: https://zijian.wang/2021/06/04/12 矩阵中的路径/
版权声明: 转载请注明出处.