题目.png
题意：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
解题思路
解法1：
1.分析题意，解决好像很简单，只需要用DFS or BFS 去搜索出来所有路径，然后判断路径是否包含结果字符串即可
2.但是容易超时，需要考虑，如何剪枝，这里我们把寻找到路径，作为flag存储起来，之后就不必要进行重新走了
3.DFS的重点在于，针对于每个位置，进行遍历前，需要将其状态值临时保存下来，然后标记为走过，等上下左右都走过之后，此位置状态值还原
解题遇到的问题
无
后续需要总结学习的知识点
无
##解法1
class Solution {
boolean flag = false;
public boolean exist(char[][] board, String word) {
if (word == null) {
return true;
}
int m = board.length;
int n = board[0].length;
char[] words = word.toCharArray();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (flag) {
break;
}
dfs(board, words, i, j, m, n, 0);
}
}
return flag;
}
private void dfs(char[][] board, char[] words, int i, int j, int m, int n,
int k) {
if (flag) {
return;
}
// 越界处理,回退
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != words[k]) {
return;
}
if (k == words.length - 1) {
// 找到答案，标记，回退
flag = true;
return;
}
// 先标记，用于后面回退
char c = board[i][j];
// 千万别忘记这步，需要把标记位走过
board[i][j] = '*';
dfs(board, words, i, j - 1, m, n, k + 1);
dfs(board, words, i + 1, j, m, n, k + 1);
dfs(board, words, i, j + 1, m, n, k + 1);
dfs(board, words, i - 1, j, m, n, k + 1);
// 回退标记位
board[i][j] = c;
}
}
