题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
样例
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false
算法1
(DFS + 回溯) $O(nm3^k)$
时间复杂度
因为要从二维矩阵中进行搜索,所以这里的时间复杂度: O(nm),n 是行数,m 是列数。在搜索到开头元素以后,还要继续往其他的三个方向进行搜索,最长搜索k(word 字符串的长度) 次,所以这里的时间复杂度:O(3^k),所以因为3 个方向的搜索过程是在每一次寻找到开头元素以后开始进行的,所以整体时间复杂度:O(nm3^k)
疑问:为什么不是4 个方向? 因为有一个方向是已经走过了的,不能够往回走,所以是3 个方向。
参考文献
https://www.bilibili.com/video/BV1M4411Q7td
Java 代码
class Solution {
private int[] x = new int[]{-1,0,1,0}, y = new int[]{0,1,0,-1};
public boolean exist(char[][] board, String word) {
//判断特殊情况
if(board.length == 0 ||board[0].length == 0 || word.length() == 0) return false;
//我们要在一个二维矩阵中进行搜索,那么必然需要对二维矩阵进行遍历
//n:行 ,m: 列
int n = board.length,m = board[0].length;
for(int x = 0; x < n; x++){
for(int y = 0; y < m; y++){
//搜索二维矩阵过程中的逻辑:
//这里就是搜索的开头: 看看二维矩阵中哪里有word 字符串的第一个字符的位置
//然后从这个找到的第一个位置一直找下去,也就是进入了dfs
//如果连word 的开头都不能在二维矩阵中找到,那么就会return false.
if(dfs(board,x,y,word,0)){
return true;
}
}
}
return false;
}
boolean dfs(char[][] board,int x,int y,String word,int index){
if(word.length() == index) return true; //说明此时已经从二维矩阵中找到了word
if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) return false; // 越界了,那么就必然找不到
if(board[x][y] != word.charAt(index)) return false; //说明当前位置不是要找的字符串中index 对应的字符
//以上的判断都不满足,说明还在寻找的过程中,并且前面都已经找到了对应的字符
//为了避免递归到原来已经扫描过的位置上,所以我们要把当前的位置的字符进行修改
board[x][y] = '.';
//以当前位置为起点,尝试往4 个方向走
for(int i = 0; i < 4; i++){
int a = this.x[i] + x;
int b = this.y[i] + y;
if (dfs(board,a,b,word,index+1)){
return true;
}
}
//能从上面的for 循环出来,说明4 个方向都走不了,那么就要进行回溯
board[x][y] = word.charAt(index);
return false;
}
}