Simple BackTracking Solution beats over 90%


  • 0
    Z

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

Log in to reply
 

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