Java short answer with backtracking and recursion, no extra spaces


  • 0
    Y
    public boolean exist(char[][] b, String word) {
            for(int i=0; i<b.length; i++)
                for(int j=0; j<b[0].length; j++)
                    if(check(b, i, j, word, 0))
                        return true;
            return false;
        }
        public boolean check(char[][] b, int i, int j, String w, int p){
            if(p == w.length()) return true;
            if(i>=0 && i<b.length && j>=0 && j<b[i].length && b[i][j] == w.charAt(p))
            {
                char t = b[i][j];
                b[i][j] = '.';
                if(check(b, i-1,j,w,p+1) || check(b, i+1,j,w,p+1) || check(b, i,j-1,w,p+1) || check(b, i,j+1,w,p+1))
                    return true;
                else
                    b[i][j] = t;
            }
            return false;
        }
    

Log in to reply
 

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