题目

剑指 Offer 12. 矩阵中的路径

思路1（回溯、DFS）

• 这题可以使用回溯+递归来解决，思路如下：
  1. 将二维数组的每一个元素都作为起点进行回溯查找
  2. 每次查找的时候，都有四个方向，但是上一个方向不能再次被遍历，因此需要将遍历过的位置进行做标记，递归返回的时候再还原
  3. 递归过程中要判断一些条件：越界直接返回false、当前字符和word中的不匹配也直接返回false
  4. 何时为匹配成功呢？只要能匹配到word的最后一个字符，即curIndex == cs.length-1（curIndex为每次搜索的深度，不过是从0开始的，就是在word中的位置；cs.length-1为最后一个字符的索引位置），因此后面剩下的就不用查找了

代码

class Solution {

    public boolean exist(char[][] board, String word) {

        char[] cs = word.toCharArray();

        // 遍历整个二维数组，即将每个字符作为第一个字符进行尝试

        for (int i = 0; i < board.length; i++) {

            for (int j = 0; j < board[0].length; j++) {

                // 只要有一条符合条件，则返回true

                if (dfs(board, cs, i, j, 0)) {

                    return true;

                }

            }

        }

        // 没找到

        return false;

    }

    public boolean dfs(char[][] board, char[] cs, int i, int j, int curIndex) {

        // 超过二维数组边界就返回false

        // 字符不匹配也直接结束递归

        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != cs[curIndex]) {

            return false;

        }

        // 如果以及全部匹配到了，就直接返回true，而不用继续匹配剩下的啦

        if (curIndex == cs.length - 1) {

            return true;

        }

        // 能递归到这里，说明当前cs中curIndex索引对应的字符和boards是匹配的

        // 因此我们需要吧遍历过的字符设置为空白，防止再次遍历

        board[i][j] = '\0';

        boolean res = dfs(board, cs, i + 1, j, curIndex + 1) ||

                      dfs(board, cs, i - 1, j, curIndex + 1) ||

                      dfs(board, cs, i, j + 1, curIndex + 1) ||

                      dfs(board, cs, i, j - 1, curIndex + 1);

        // 回溯的时候要把原来设置为空白字符的还原

        board[i][j] = cs[curIndex];

        // 只要出现true，就一路返回

        return res;

    }

}

复杂度分析

• 时间复杂度：\(O(MN·3^K)\)，二维数组共有M·N个起点；然后对于每个起点来说，每步都有三个方向可以选择（不包括上一个方向），最长要走的步数就是word的长度K，因此复杂度为\(3^K\)
• 空间复杂度：\(O(K)\)，递归深度最深也就是word的长度