public boolean exist(char[][] board, String word) {

if (word.length() == 0) {

return true;

}

if (board.length == 0) {

return false;

}

int m = board.length;

int n = board[0].length;

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

boolean[][] visited = new boolean[m][n];

if (helper(i, j, 0, board, word, visited)) {

return true;

}

}

}

return false;

}

private boolean helper(int i, int j, int index, char[][] board, String word, boolean[][] visited) {

if (index >= word.length()) {

return true;

}

if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {

return false;

}

if (visited[i][j] || board[i][j] != word.charAt(index)) {

return false;

}

visited[i][j] = true;

if (helper(i, j+1, index + 1, board, word, visited) ||

helper(i+1, j, index + 1, board, word, visited) ||

helper(i, j-1, index + 1, board, word, visited) ||

helper(i-1, j, index + 1, board, word, visited)) {

return true;

}

visited[i][j] = false;

return false;

}

/**

public boolean exist2(char[][] board, String word) {

if (word.length() == 0) {

return true;

}

if (board.length == 0) {

return false;

}

int m = board.length;

int n = board[0].length;

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (helper(i, j, 0, board, word)) {

return true;

}

}

}

return false;

}

private boolean helper(int i, int j, int index, char[][] board, String word) {

if (index >= word.length()) {

return true;

}

if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {

return false;

}

if (board[i][j] != word.charAt(index)) {

return false;

}

board[i][j] ^= 256;

if (helper(i, j+1, index + 1, board, word) ||

helper(i+1, j, index + 1, board, word) ||

helper(i, j-1, index + 1, board, word) ||

helper(i-1, j, index + 1, board, word)) {

return true;

}

board[i][j] ^= 256;

return false;

}