79. 单词搜索/面试题12. 矩阵中的路径(一般)

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

1
2
3
4
5
6
7
8
9
10
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search

思路：

深搜回溯

我们从矩阵左上角开始搜索

深搜：

  1. 先向下深搜，如果超过行高了，搜索失败，或者已经访问过了，剪枝，返回false
  2. 再向上深搜，如果行小于0了，越界了，或者已经访问过了，访问失败，返回false；
  3. 再向左深搜，如果列小于0，越界，或者已经访问过，访问失败，返回false；
  4. 最后向右深搜，如果超过列宽，或者已经访问过了，访问失败，返回false；

具体思路可参考

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/

复杂度分析：
M,N 分别为矩阵行列大小， K 为字符串 word 长度。

时间复杂度 O(3^K MN)： 最差情况下，需要遍历矩阵中长度为 K 字符串的所有方案，时间复杂度为 O(3^K)；矩阵中共有 MN 个起点，时间复杂度为 O(MN)。
方案数计算： 设字符串长度为 K ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 33 种选择，因此方案数的复杂度为 O(3
K
) 。
空间复杂度 O(K) ： 搜索过程中的递归深度不超过 K ，因此系统因函数调用累计使用的栈空间占用 O(K)（因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K=MN ，递归深度为 MN ，此时系统栈使用 O(MN) 的额外空间。

回看记录200714

嗯，会写和写出来感觉不一样，记得多写

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] cword = word.toCharArray();
        int row = board.length;
        int col = board[0].length;
        if(board==null || row==0 || col==0 || board[0]==null){
            return false;
        }
        //定义访问数组
        boolean[][] isvisited = new boolean[row][col];
        for (int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                //如果找到值，开始深搜
                if(board[i][j]== cword[0]){
                    //如果深搜找到了，返回true
                    if(dfs(board,cword,isvisited,i,j,0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    //深搜回溯
    boolean dfs(char[][] board,char[] cword,boolean[][] isvisted,int row,int col,int index){
        //如果行，列越界,如果已经被访问，如果值不相等
        if(row<0 || row >= board.length
          || col<0 || col >=board[0].length
          || isvisted[row][col] || board[row][col]!=cword[index]){
            return false;
        }
        //如果这个数全部找到了，也就是index找到头了
        if(index==cword.length-1){
            return true;
        }
        //回溯
        isvisted[row][col]=true;
        //上下左右尝试
        boolean b = dfs(board,cword,isvisted,row-1,col,index+1)
                || dfs(board,cword,isvisted,row+1,col,index+1)
                || dfs(board,cword,isvisted,row,col-1,index+1)
                || dfs(board,cword,isvisted,row,col+1,index+1);
        isvisted[row][col]=false;
        return b;
    }
}