矩阵中的路径

题目：

题解：

1、深度优先搜索（DFS）+ 剪枝

解题思路：本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝 解决。
- 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
- 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。
解题中主要出现的问题：
- board[i][j] = '\0';
  
  使用空字符（Python: ‘’ , Java/C++: ‘\0’ ）做标记是为了防止标记字符与矩阵原有字符重复。当存在重复时，此算法会将矩阵原有字符认作标记字符，从而出现错误。
- board[i][j] = word[k];
  
  递归搜索匹配字符串过程中，需要 board[i][j] = '\0' 来防止 ”走回头路“ 。当匹配字符串不成功时，会回溯返回，此时需要board[i][j] = tmp 来”取消对此单元格的标记”。在DFS过程中，每个单元格会多次被访问的， board[i][j] = '\0'只是要保证在当前匹配方案中不要走回头路。
复杂度分析：

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

代码：

// 深度优先搜索（DFS）+ 剪枝
class Solution {
    public boolean exist(char[][] board, String word) {
        // 将String类型的word变成char数组
        char[] words = word.toCharArray();


        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board,words,i,j,0)) return true;
            }
        }
        return false;
    }

    // 深度优先搜索
    private boolean dfs(char[][] board, char[] words, int i, int j, int k) {
        // 当i，j超出边界，或矩阵中i行j列的元素不等于word第k个char，返回false
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != words[k]) return false;
        // 当k为最后一位，因为前面判断了board[i][j] != words[k]，所以返回true
        if(k == words.length - 1) return true;
        // 使用空字符（Python: '' , Java/C++: '\0' ）做标记是为了防止标记字符与矩阵原有字符重复。
        // 当存在重复时，此算法会将矩阵原有字符认作标记字符，从而出现错误。
        board[i][j] = '\0';
        // 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，
        // 使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
        boolean res = dfs(board,words,i - 1,j,k+1) || dfs(board,words,i ,j - 1,k+1)
                || dfs(board,words,i + 1,j,k+1) || dfs(board,words,i ,j + 1,k+1);
        // 递归搜索匹配字符串过程中，需要 board[i][j] = '\0' 来防止 “走回头路” 。
        // 当匹配字符串不成功时，会回溯返回，此时需要board[i][j] = tmp 来“取消对此单元格的标记”。
        // 在DFS过程中，每个单元格会多次被访问的，
        // board[i][j] = '\0'只是要保证在当前匹配方案中不要走回头路。
        board[i][j] = words[k];

        return res;
    }
}