题目
题目链接
题解
class Solution {
public boolean exist(char[][] board, String word) {
if (board.length * board[0].length < word.length()) {
return false;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (search(board, word, 0, i, j)) {
return true;
}
}
}
return false;
}
/**
* dfs
* @param board 矩阵
* @param word 字符串
* @param i 行
* @param j 列
* @return 结果
*/
private static boolean search(char[][] board, String word, int index, int i, int j) {
if (word.length() - 1 == index && board[i][j] == word.charAt(index)) {
return true;
}
if (word.length() - 1 == index) {
return false;
}
if (board[i][j] != word.charAt(index)) {
return false;
}
char cache = board[i][j];
board[i][j] = '-';
// 上
if (i - 1 >= 0 && board[i - 1][j] != '-') {
if (search(board, word, index + 1, i - 1, j)) {
return true;
}
}
// 左
if (j - 1 >= 0 && board[i][j - 1] != '-') {
if (search(board, word, index + 1, i, j - 1)) {
return true;
}
}
// 下
if (i + 1 < board.length && board[i + 1][j] != '-') {
if (search(board, word, index + 1, i + 1, j)) {
return true;
}
}
// 右
if (j + 1 < board[i].length && board[i][j + 1] != '-') {
if (search(board, word, index + 1, i, j + 1)) {
return true;
}
}
board[i][j] = cache;
return false;
}
}