# Simple BackTracking Solution beats over 90%

• basic backtracking theory, feel free to let me know for any questions or improvements~

``````public class Solution {
boolean res = false;
public boolean exist(char[][] board, String word) {
boolean[][] chose = new boolean[board.length][board[0].length];
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[i].length; j++){
if(word.charAt(0) == board[i][j]){
chose[i][j] = true;
bt(board, word, i, j, 1, chose);
chose[i][j] = false;
}
if(res) return res;
}
}
return res;
}
private void bt(char[][] board, String word, int i, int j, int start, boolean[][] chose){
if(start == word.length()) res = true;
if(!res){
if(i < board.length && j + 1 < board[i].length && !chose[i][j + 1] && board[i][j + 1] == word.charAt(start)){
chose[i][j + 1] = true;
bt(board, word, i, j + 1, start + 1, chose);
chose[i][j + 1] = false;
}
if(i + 1 < board.length && j < board[i].length && !chose[i + 1][j] && board[i + 1][j] == word.charAt(start)){
chose[i + 1][j] = true;
bt(board, word, i + 1, j, start + 1, chose);
chose[i + 1][j] = false;
}
if(i - 1 >= 0 && j  < board[i].length && !chose[i - 1][j] && board[i - 1][j] == word.charAt(start)){
chose[i - 1][j] = true;
bt(board, word, i - 1, j, start + 1, chose);
chose[i - 1][j] = false;
}
if(i < board.length && j - 1 >= 0 && !chose[i][j - 1] && board[i][j - 1] == word.charAt(start)){
chose[i][j - 1] = true;
bt(board, word, i, j - 1, start + 1, chose);
chose[i][j - 1] = false;
}
}
}
}
``````

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