剑指 Offer 12. 矩阵中的路径（medium）

• • • 方法一：递归 + 回溯 + 剪枝

方法一：递归 + 回溯 + 剪枝

思路：本题提供了一个矩阵，矩阵是一个二维数组，需要我们在二维数组中进行搜索，为了能够覆盖所有的情况，必然要使用两个嵌套for循环。
在搜索过程中，当遇到匹配成功的元素，搜索其下一元素的操作与当前的操作一致，即可以使用递归。
递归参数：
当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在word 中的索引 idx 。
终止条件：
返回 false：
(1) 行或列索引越界

(2) 当前矩阵元素与目标字符不同

(3) 当前矩阵元素已访问过

返回 true： idx == len(word) - 1 ，即字符串 word 已全部匹配。

递推工作：
标记当前矩阵元素： 将 board[ i ] [ j ] 修改为特殊字符 '\0'，代表此元素已访问过，防止之后搜索时重复访问。
搜索下一节点： 朝当前元素的 上、左、下、 右四个方向开启下层递归。
回退时还原当前矩阵元素： 将 board[ i ] [ j ] 元素还原至初始值，即 word[idx] 。
返回值： 返回布尔量 res ，代表是否搜索到目标字符串。

class Solution {
    public boolean exist(char[][] board, String word) {
        // 先将字符串进行拆分，一个一个元素进行匹配
        char[] words = word.toCharArray();
        // 通过两层嵌套for，覆盖所有的情况
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 以该元素为起始点，递归检查是否符合要求
                if (helper(i, j, 0, board, words)) return true;
            }
        }
        // 检查所有的矩阵元素，都没有匹配上的，返回false。
        return false;
    }
    boolean helper(int i, int j, int idx, char[][] board, char[] word) {
        // 边界条件（1）行越界（2）列越界（3）矩阵元素已经被访问过
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word[idx]) {
            return false;
        }
        // 成功匹配目标字符串，返回true
        if (idx == word.length - 1) {
            return true;
        }
        // 将当前矩阵元素进行标记，代表已经访问过，防止后续递归重复访问。
        
        board[i][j] = '\0';
        // 搜索元素的四个方向，下，上，右，左，匹配下一个目标元素
        boolean res = helper(i + 1, j, idx + 1, board, word) 
                || helper(i - 1, j, idx + 1, board, word) 
                || helper(i, j + 1, idx + 1, board, word) 
                || helper(i, j - 1, idx + 1, board, word);
        // 回溯，恢复当前矩阵元素。
        board[i][j] = word[idx];
        
        // 返回结果
        return res;
    }
}

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

总结：就差一点就写出来了，没想到双重for循环以及回溯，这类题还需要提高敏感性。
参考阅读：

1. 最优解.
2. 图解.