7ms Java solution without extra space


  • 0
    A

    The basic idea here is that each time you meet the appearance of the first element of the word, then you start to do recursion. In each recursion, you check your top, down, left, right four neighbors, to see which one is same as the next character, then next recursion starts. Also, remember to mark current position in board to indicate that you have traversed this position, to avoid repeated use of one character, like this :

    board: [ a, a] | word: "aaa"

    If you forget to mark path, you will go between (0,0) and (0,1) several times and then get an True but which is a wrong answer.

    public class Solution {
        public boolean exist(char[][] board, String word) {
            boolean res = false;
            char[] arr = word.toCharArray();
            
            for(int i=0; i<board.length; ++i) 
                for(int j=0;j<board[0].length;++j) 
                    if(board[i][j] == arr[0]) 
                        if (recursion(board,i,j,0,1,arr))
                            return true;
                    
            return false;
        }
        
        public boolean recursion(char[][] board, int row, int col, int index, int nxtIndex, char[] arr) {
            if(nxtIndex == arr.length)
                return true;
            int top = row-1, down = row+1, left = col-1, right = col+1;
            board[row][col] = '0';
            
            if( top >= 0 && top < board.length && board[top][col] == arr[nxtIndex]) 
                if( recursion(board,top,col,nxtIndex,nxtIndex+1,arr)) 
                    return true;
        
            if( down >= 0 && down < board.length && board[down][col] == arr[nxtIndex]) 
                if(recursion(board,down,col,nxtIndex,nxtIndex+1,arr))
                    return true;
            
            if( left >= 0 && left < board[0].length && board[row][left] == arr[nxtIndex]) 
                if(recursion(board,row,left,nxtIndex,nxtIndex+1,arr))
                    return true;
                
            if( right >= 0 && right < board[0].length && board[row][right] == arr[nxtIndex]) 
                if( recursion(board,row,right,nxtIndex,nxtIndex+1,arr))
                    return true;
            
            board[row][col] = arr[index];
            return false;
        }
        
    }
    

Log in to reply
 

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