public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length < 1 || board[0].length < 1) return false;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if(dfs(board, i, j, word, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, String word, int start) {
if (start == word.length()) {
return true;
}
int row = board.length;
int col = board[0].length;
if (i < 0 || j < 0 || i >= row || j >= col || board[i][j] != word.charAt(start)) {
return false;
}
board[i][j] ^= 256;
boolean res = dfs(board, i - 1, j, word, start + 1) || dfs(board, i, j - 1, word, start + 1) || dfs(board, i + 1, j, word, start + 1) || dfs(board, i, j + 1, word, start + 1) ;
board[i][j] ^= 256;
return res;
}
}
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0)
return false;
if (word == null || word.length() == 0)
return true;
char[] wordArray = word.toCharArray();
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == wordArray[0] && existWord(board, i, j, wordArray, 1))
return true;
}
}
return false;
}
private boolean existWord(char[][] board, int i, int j, char[] word, int index) {
if (index == word.length)
return true;
char stored = board[i][j];
board[i][j] = '*';
boolean exist = i > 0 && board[i - 1][j] == word[index] && existWord(board, i - 1, j, word, index + 1)
|| i + 1 < board.length && board[i + 1][j] == word[index] && existWord(board, i + 1, j, word, index + 1)
|| j > 0 && board[i][j - 1] == word[index] && existWord(board, i, j - 1, word, index + 1)
|| j + 1 < board[0].length && board[i][j + 1] == word[index] && existWord(board, i, j + 1, word, index + 1);
board[i][j] = stored;
return exist;
}
}