题目
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串
“bfce”
的路径(路径中的字母用加粗标出)。
1
2
3 [["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]但矩阵中不包含字符串
“abfb”
的路径,因为字符串的第一个字符b
占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。示例 1:
1
2 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true示例 2:
1
2 输入:board = [["a","b"],["c","d"]], word = "abcd"
输出:false提示:
1 <= board.length <= 200
1 <= board[i].length <= 200
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
回溯法非常适合有多个步骤组成的问题,并且每个步骤都有个多个选择。
由于这不是一个最优问题,而是要找到满足条件的解,我们不得不遍历所有可能的解,用剪枝来优化,这就是回溯。
- 我们首先选择一个与字符串首字母匹配的位置开始;
- 因为有限制条件:不能重复进入格子,我们还要用一种方法来标记已经进入过的格子;
每来到一个新的格子,我们有如下选择:
- 已经找到了,返回
- 还没找到,但这个格子来过,返回
- 还没找到,这个格子不符合条件,返回
- 还没找到,这个格子符合条件,继续找;
1 | class Solution { |
中间出现的问题是,没有考虑到矩阵大小$1×1$的特殊情况。
很明显的优化是可以把mark
矩阵省略,通过用临时变量保存当前位置值…..想到了但是又钻牛角尖了。
1 | class Solution { |