One more DFS-Backtracking solution in Java (15ms)


  • 0
    G

    I think below approach is self explanatory :

    public class Solution {
        public boolean exist(char[][] board, String word) {
            boolean ans = false;
            boolean[][] visited = new boolean[board.length][board[0].length];
            for(int i=0;i<board.length;i++){
                for(int j=0;j<board[0].length;j++){
                    if(board[i][j]==word.charAt(0)){
                        visited[i][j] = true;
                        ans = checkString(board,i,j,word.substring(1),visited);
                        if (ans) {
                            return true;
                        } else {
                            visited[i][j] = false;
                        }
                    }
                }
            }
            return false;
        }
        
        private boolean checkString(char[][] board,int i,int j, String word,boolean[][] visited){
            //System.out.println("Checking for String " + word + " at index a["+i+"]["+j+"]");
            if(word.length()==0) return true;
            boolean res = false;
            if(i<board.length-1 && !visited[i+1][j] && board[i+1][j]==word.charAt(0)){
                visited[i+1][j] = true;
                res = checkString(board,i+1,j,word.substring(1),visited);
                if (res) {
                    return true;
                } else {
                    visited[i+1][j] = false;
                }
            }
            if(i>0 && !visited[i-1][j] && board[i-1][j]==word.charAt(0)){
                visited[i-1][j] = true;
                res = checkString(board,i-1,j,word.substring(1),visited);
                if (res) {
                    return true;
                }else {
                    visited[i-1][j] = false;
                }   
            }
            if(j<board[0].length-1 && !visited[i][j+1] && board[i][j+1]==word.charAt(0)){
                visited[i][j+1] = true;
                res = checkString(board,i,j+1,word.substring(1),visited);    
                if (res) {
                    return true;
                } else {
                    visited[i][j+1] = false;
                }      
            } 
            if(j>0 && !visited[i][j-1] && board[i][j-1]==word.charAt(0)){
                visited[i][j-1] = true;
                res = checkString(board,i,j-1,word.substring(1),visited);   
                if (res) {
                    return true;
                } else {
                    visited[i][j-1] = false;
                }  
            } 
            return false;
        }
    }
    
    

  • 0
    M

    @ganesh9
    Just FYI: substring() is an O(n) operation for Java 1.7+


Log in to reply
 

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