Backtracking Java Solution


  • 0
    P
    public class Solution {
        public boolean exist(char[][] board, String word) {
            if(word.length() == 0 || board.length == 0 )
                return false;
            
            int rows = board.length, columns = board[0].length, wordLen = word.length();
            int[][] dp = new int[board.length][board[0].length];
            int currX,currY,counter = 0;
            for(int i = 0; i < board.length ; i++){
                for(int j = 0 ; j<board[0].length ; j++){
                    if(String.valueOf(board[i][j]).equals(word)){
                        return true;
                    }
                    if(board[i][j] == word.charAt(counter)){
                        dp[i][j] = 1;
                        counter++;
                        if(isPresent(board,word,dp,counter, i , j+1,rows,columns,wordLen)
                           || 
                           isPresent(board,word,dp,counter, i , j-1,rows,columns,wordLen)
                           ||
                           isPresent(board,word,dp,counter, i-1 , j,rows,columns,wordLen)
                           ||
                           isPresent(board,word,dp,counter, i+1 , j,rows,columns,wordLen))
                           
                            return true;
                        else{
                            dp[i][j] = 0;
                            counter--;
                        }
                    }
                }
            }
            
            return false;
        }
        
        
        boolean isPresent(char[][] board, String word,int[][] dp,int counter, int currX, int currY,int rows,int columns, int wordLen){
            if(currX < 0 || currX >= rows)
                return false;
            
            if(currY < 0 || currY >= columns)
                return false;
            
            if (word.charAt(counter) == board[currX][currY]){
                if(dp[currX][currY] == 0 && counter == wordLen -1 )
                    return true;
                    
                else if(dp[currX][currY] == 0){
                    counter++;
                    dp[currX][currY] = 1;
                    if(    isPresent(board,word,dp,counter, currX , currY+1,rows,columns,wordLen)
                           || 
                           isPresent(board,word,dp,counter, currX , currY-1,rows,columns,wordLen)
                           ||
                           isPresent(board,word,dp,counter, currX-1 , currY,rows,columns,wordLen)
                           ||
                           isPresent(board,word,dp,counter, currX+1 , currY,rows,columns,wordLen)){
                               return true;
                           }
                    else{
                        dp[currX][currY] = 0;   
                    }
                }
                
            }
            return false;
            
        }
    }
    

Log in to reply
 

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