79. 单词搜索
难度中等820
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
代码语言：javascript复制board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 falseDFS
代码语言：javascript复制class Solution {
private static final int[][] DIR = {
{
-1, 0}, {
0, -1}, {
0, 1}, {
1, 0}};
private int rows;
private int cols;
private int len;
private boolean[][] visied;
private char[] charArray;
private char[][] board;
public boolean exist(char[][] board, String word) {
rows = board.length;
cols = board[0].length;
if (rows == 0) {
return false;
}
visied = new boolean[rows][cols];
this.len = word.length();
this.charArray = word.toCharArray();
this.board = board;
for (int i = 0; i < rows; i ) {
for (int j = 0; j < cols; j ) {
if (dfs(i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(int x, int y, int begin) {
if (begin == len - 1) {
return board[x][y] == charArray[begin];
}
if (board[x][y] == charArray[begin]) {
visied[x][y] = true;
for (int i = 0; i < DIR.length; i ) {
int newx = x DIR[i][0];
int newy = y DIR[i][1];
if (inArea(newx, newy) && !visied[newx][newy]) {
if (dfs(newx, newy, begin 1)) {
return true;
}
}
}
visied[x][y] = false;
}
return false;
}
private boolean inArea(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
}
