Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
题意：给定一个字符类型的二维数组和一个单词，在这个数组里能不能找到这个单词，单词在这个二维矩阵里需要时一条连续的路径。
思路：虽然看起来和77、78题不一样了，但是本质上仍然是一个深度优先搜索的题目。查找的index变为了单词中指向每个字符的指针，搜索的范围变成了这个二维矩阵。遍历二维矩阵每个字符，都尝试把他当做是单词的首字母，每次搜到一个匹配的字符后，将指针指向单词下一个字符，待搜索的范围是之前字符的临接字符。
static boolean[][] visited;
public boolean exist(char[][] board, String word) {
visited = new boolean[board.length][board[0].length];
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[i].length; j++){
if(search(board, word, i, j, 0)){
return true;
}
}
}
return false;
}
private boolean search(char[][]board, String word, int i, int j, int index){
if(index == word.length()){
return true;
}
if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
return false;
}
visited[i][j] = true;
if(search(board, word, i-1, j, index+1) ||
search(board, word, i+1, j, index+1) ||
search(board, word, i, j-1, index+1) ||
search(board, word, i, j+1, index+1)){
return true;
}
visited[i][j] = false;
return false;
}