79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false提示：
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
解法一
DFS
class Solution {
private int[] dx = new int[]{1, -1, 0, 0};
private int[] dy = new int[]{0, 0, 1, -1};
public boolean exist(char[][] board, String word) {
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, visited, i, j, "")) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, boolean[][] visited, int i, int j, String str) {
// terminator
if (str.length() == word.length()) return str.equals(word);
if (i > board.length - 1 || i < 0 || j > board[0].length - 1 || j < 0) return false;
if (visited[i][j]) return false;
// process
str += board[i][j];
// 这里不做剪枝会超时
if (!str.equals(word.substring(0, str.length()))) return false;
// drill down
visited[i][j] = true;
for (int k = 0; k < dx.length; k++) {
if (dfs(board, word, visited, i + dx[k], j + dy[k], str)) return true;
}
// reverse
visited[i][j] = false;
return false;
}
}