DFS Backtracking solution in Java (14ms)

• ``````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;
}

boolean result = false;

for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(word.charAt(0) == board[i][j]) {
result = DFS(board, word, 0, i, j);
//might start from more than one positions, but once a solution if found, return true immediately
if(result) {
return result;
}
}
}
}
return result;
}

public boolean DFS(char[][] board, String word, int k, int i, int j) {
if(k == word.length()) {
return true;
}

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

if(board[i][j] != word.charAt(k)) {
return false;
}

board[i][j] = '#'; //mark the position

boolean result = DFS(board, word, k + 1, i + 1, j)
|| DFS(board, word, k + 1, i - 1, j)
|| DFS(board, word, k + 1, i, j + 1)
|| DFS(board, word, k + 1, i, j - 1);

board[i][j] = word.charAt(k); //restore the char in the board, might be used in next search

return result;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.