剑指offer 12 矩阵中的路径
难度：中等
题目详情
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
示例 1：
输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true
示例 2：
输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出：false
提示：
- 1 <= board.length <= 200
- 1 <= board[i].length <= 200
- board 和 word 仅由大小写英文字母组成
思路
看到这道题，我首先想到的是动态规划，但是稍微分析一下就可以判断出，此题不能用动态规划来解。
如果依据动态规划，根据动态规划原理，
首先要确定动态规划数组的状态，也就是表中的字母是否出现在word中，出现则是true。
下一步确定转移方程
如果最后一个字母满足，问题也就化成了找word[n-1]中的字符匹配，直到找到所有的字母。
在找动态规划数组与子问题之间的关系时，找不到。因此动态规划不成立。
因此接下来我想到的是深度优先搜索。因为会遍历每一个元素，所以这种算法一定可以完成题目要求。
开干！！!
每一个数组元素有上、下、左、右四个方向可以连接，深度优先搜索就是
先朝一个方向搜索到底，再回溯查找其他方向。
DFS递归：
参数
原始数组board ，单词word，原始数组索引i，j，word索引 k
递归肯定要先确定终止条件：
终止条件：
- 返回false
- 索引越界
- 数组中的字母不是单词中对应的字母
- 数组已经被访问了（剪枝）
其实只有1，2也可以得出正确结果，条件3只是用作提高程序效率。
- 返回true
查找到单词最后一个字母，也就是k=word.length-1;
递归内容：
- 对应终止条件3，为了完成剪枝操作，需要标记已经被访问的数组。这里没必要新开辟一个数组，可以在数组本身上标记，将访问后的数组的值置为一个不可能出现在单词中的值就行，本文置为了’\n’。
- 搜索下一个元素：上下左右四个方向进行递归，当出现一个单词满足要求，就结束扫描，结束DFS。这里借助了||的断路特性，只要有true，后面的代码就不用执行，直接返回true。
代码
public boolean exist(char[][] board, String word) {
char[] chars = word.toCharArray();
int n = board.length;
int m = board[0].length;
for(int i = 0;i<n;i++){
for(int j = 0; j< m; j++){
if(board[i][j]==chars[0]){
if(dfs(board,i,j,chars,0)){
return true;
}
}
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, char[] word, int k) {
if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
if(k == word.length - 1) return true;
board[i][j] = '\n';
boolean res = dfs(board, i + 1, j,word, k + 1) || dfs(board, i - 1, j, word, k + 1) ||
dfs(board, i, j + 1, word, k + 1) || dfs(board, i , j - 1, word,k + 1);
board[i][j] = word[k];
return res;
}
算法复杂度
空间复杂度：O(K)，O(MN)
- 没有使用额外的数组空间，堆内存O(1)
- 使用了递归，递归深度与单词长度有关，深度最深也就是单词长度K，栈内存O(K)。最坏情况：当单词长度K>=MN时，每个数组元素都产生递归，此时O(K)=O(MN)。
时间复杂度 O(3^KMN)
- 最差情况下，需要遍历矩阵中长度为 K 字符串的所有方案，时间复杂度为 O(3^K)；矩阵中共有 MN 个起点，时间复杂度为 O(MN) 。
- 方案数计算： 设字符串长度为 K ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 3 种选择，因此方案数的复杂度为 O(3^K)