My 10 second java solution. The code is long but the idea behind it is simple and easy to understand.


  • 0
    Y
    public class Solution {
        boolean result=false;
        boolean keep=true;
        public boolean exist(char[][] board, String word) {
            if(word.length()==0){
                return true;
            }
            if(board==null||board.length==0||board[0].length==0){
                return false;
            }
            boolean[][] use=new boolean[board.length][board[0].length];
            helper (board,word,use,0,false,0,0);
            return result;
        }
        private void helper(char[][]board,String word, boolean [][] use, int counter, boolean second,int row, int col){
            if(counter==word.length()){
                result=true;
                keep=false;
                return;
            }
            if(second==false && keep==true){
             for(int i=0;i<board.length;i++){
                 for(int j=0;j<board[0].length;j++){
                  if(board[i][j]==word.charAt(counter)&&use[i][j]==false){
                      use[i][j]=true;
                      counter++;
                      second=true;
                      row=i;
                      col=j;
                      helper(board,word,use,counter,second,row,col);
                      second=false;
                      counter--;
                      use[i][j]=false;
                  }
                 }
             }
            }
            if (second==true&& keep==true){
                if(row!=0&& board[row-1][col]==word.charAt(counter)&&use[row-1][col]==false){
                    use[row-1][col]=true;
                    counter++;
                    row--;
                    helper(board,word,use,counter,second,row,col);
                    row++;
                    counter--;
                    use[row-1][col]=false;
                }
                if(row!=(board.length-1)&& board[row+1][col]==word.charAt(counter)&&use[row+1][col]==false){
                    use[row+1][col]=true;
                    counter++;
                    row++;
                    helper(board,word,use,counter,second,row,col);
                    row--;
                    counter--;
                    use[row+1][col]=false;
                }
               if(col!=0&& board[row][col-1]==word.charAt(counter)&&use[row][col-1]==false){
                    use[row][col-1]=true;
                    counter++;
                    col--;
                    helper(board,word,use,counter,second,row,col);
                    col++;
                    counter--;
                    use[row][col-1]=false;
                }
                if(col!=(board[row].length-1)&& board[row][col+1]==word.charAt(counter)&&use[row][col+1]==false){
                    use[row][col+1]=true;
                    counter++;
                    col++;
                    helper(board,word,use,counter,second,row,col);
                    col--;
                    counter--;
                    use[row][col+1]=false;
                }
                else{
                    return;
                }
            }
         }
    }

Log in to reply
 

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