剑指Offer刷题记录，第八题。
剑指 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(3KMN), 最差情况下，需要遍历矩阵中长度为K字符串的所有方案，时间复杂度为O(3K)；矩阵***有MN个起点，时间复杂度为O(MN),因此，总的时间复杂度为O(3KMN)。（方案数计算：设字符串长度为K，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下三种选择，因此方案数的复杂度为O(3K)。）
空间复杂度： O(K), 搜索过程中的递归深度不超过K，因此系统因函数调用累计使用的栈空间占用O(K)。最坏情况下K = MN, 递归深度为MN,此时系统栈调用O(MN)的额外空间。
总结：就差一点就写出来了，没想到双重for循环以及回溯，这类题还需要提高敏感性。
参考阅读：
