Simple Java recursion with backtracking


  • 0
    L
       public boolean exist(char[][] board, String word) {
            for(int i=0;i<board.length;i++) {
                for(int j=0;j<board[i].length;j++) {
                   if(helper(board,word,i,j,0)) {
                       return true;
                   } 
                }
            }
            return false;
        }
        
        private boolean helper(char[][] board, String word, 
                               int i, int j, int counter) {
            if(counter==word.length()) {
                return true;
            }
            if(board[i][j]=='#' || word.charAt(counter)!=board[i][j]) {
                return false;
            }
    
            char c = board[i][j];
            board[i][j]='#';
    
            
            //go right.
            if(j<board[i].length-1) {
                if(helper(board,word,i,j+1,counter+1)) {
                    return true;
                }
            }
            
            //go left.
            if(j>0) {
                if(helper(board,word,i,j-1,counter+1)) {
                    return true;
                }
            }
            
            //go up.
            if(i>0) {
                if(helper(board,word,i-1,j,counter+1)) {
                    return true;
                }
            }
            
            //go down.
            if(i<board.length-1) {
                if(helper(board,word,i+1,j,counter+1)) {
                    return true;
                }
            }
            
            board[i][j]=c;
            if (counter == word.length() - 1) {
              return true;
            }        
            return false;
        }
    

Log in to reply
 

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