题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串bfce的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],["s","f","c","s"],["a","d","e","e"]]
但矩阵中不包含字符串abfb的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
示例 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
解题思路
方法：DFS+剪枝
时间复杂度：$O(3^KMN)$ 最差情况下，需要遍历矩阵中长度为 $K$ 字符串的所有方案，时间复杂度为 $O(3^K)$；矩阵中共有 $MN$个起点，时间复杂度为 $O(MN)$。
空间复杂度：$O(K)$ 搜索过程中的递归深度不超过 $K$ ，因此系统因函数调用累计使用的栈空间占用 $O(K)$
代码如下
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for(int i=0; i<board.size(); i++){
for(int j=0; j<board[i].size(); j++){
if(board[i][j] == word[0]){
if(dfs(i,j,board,word,0))
return true;
}
}
}
return false;
}
bool dfs(int i,int j,vector<vector<char>>& board, string word,int word_index){
if(i<0||i>=board.size()||j<0||j>=board[i].size() || board[i][j]!=word[word_index]){
return false;
}
if(word.size()-1 == word_index){
return true;
}
char tmp = board[i][j];
board[i][j] = '.';
bool judge = dfs(i+1,j,board,word,word_index+1)||dfs(i,j+1,board,word,word_index+1)
||dfs(i-1,j,board,word,word_index+1)||dfs(i,j-1,board,word,word_index+1);
board[i][j] = tmp;
return judge;
}
};
解法分析
- 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。
DFS通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。 - 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。
算法剖析
- 终止条件
- 行列越界
- 矩阵元素和目标元素不同
- 当前元素已经访问过
- 递推过程
- 遍历一遍二维数组，找到第一个匹配的元素
- 将当前元素暂存于
tmp变量中，修改当前变量为/。这么做代表这个元素已经访问过，后面无需再重新访问 - 对当前元素上下左右进行递归
- 将当前变量还原
