共计 1628 个字符，预计需要花费 5 分钟才能阅读完成。
题目：
Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacentcell, where “adjacent” cells are those horizontally or verticallyneighboring. The same letter cell may not be used more than once.
Example:
board = [[‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’], [‘A’,’D’,’E’,’E’] ]
Given word = “ABCCED”, return true. Given word = “SEE”, return true.Given word = “ABCB”, return false.
这是一道搜索题，用 backtracking 做，问题就是怎样设计这个回溯过程。我们需要的就是在这个二维数组里面一个个寻找每个字符，所以 dfs 的终止条件是当我们把每个字符全部搜索了，也就是 index==word.length。因为每个字符只能使用一次所以我们还需要一个 visited 数组来记录当前元素是否被访问过，如果我们找到了和当前搜索的字符相匹配的元素，我们就要上下左右搜索四个方向。这么看来思路还是很清晰的，但是我在做这一题时被几点困扰：1. 我们需要遍历二维数组，但同时我们又需要移动移动被搜索字符串的 index，一开始我是把遍历二维数组和移动字符串的 index 写在了同一个 dfs 的 recursion 里面然后接下去我就没办法写了，看了 discuss 之后才知道应该把遍历二维数组写在主函数里面，让它来调用 dfs。2. 选择下一个可以走的 adjacent，我一开始还在想需不需要用一个 list 来存储每一步可以走的 adjacent，这样的话就太麻烦了，还需要分情况讨论，但其实是没有必要的。我们把这些判断都加在 recursion 的终止条件里面就好了。
代码如下：
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < board.length; i ++) {
for (int j = 0; j < board[0].length; j ++) {
if (word.charAt(0) == board[i][j] && dfs(board, word, visited, 0, i, j))
return true;
}
}
return false;
}
public boolean dfs(char[][] board, String word, boolean[][] visited, int index, int row, int col) {
if (index == word.length()) return true;
if (row == board.length || row < 0 || col == board[0].length || col < 0 || visited[row][col] || word.charAt(index) != board[row][col]) return false;
visited[row][col] = true;
if (dfs(board, word, visited, index+1, row+1, col) ||
dfs(board, word, visited, index+1, row, col+1) ||
dfs(board, word, visited, index+1, row-1, col) ||
dfs(board, word, visited, index+1, row, col-1))
return true;
visited[row][col] = false;
return false;
}
}
