给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
dfs+回溯算法
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j++) {
if (word.charAt(0) == board[i][j]) {
if (helper(board, i, j, word, 0, new boolean[m][n])) return true;
}
}
}
return false;
}
private boolean helper(char[][] board, int row, int column, String word, int index, boolean[][] visited) {
//匹配成功
if (index == word.length()) return true;
//越界
if (row < 0 || column < 0 || row >= board.length || column >= board[0].length) return false;
//当前已经被访问过
if (visited[row][column]) return false;
//当前不匹配
if (board[row][column] != word.charAt(index)) return false;
//当前匹配，记录已经访问过
visited[row][column] = true;
//寻找接下来的字符（上下左右）
if (helper(board, row + 1, column, word, index + 1, visited) ||
helper(board, row - 1, column, word, index + 1, visited) ||
helper(board, row, column - 1, word, index + 1, visited) ||
helper(board, row, column + 1, word, index + 1, visited)) return true;
visited[row][column] = false;
return false;
}
}视频：
https://www.bilibili.com/video/av53982318?from=search&seid=17404693731891749063