DFS Backtracking solution in Java (14ms)


  • 1
    Y
    public class Solution {
        public boolean exist(char[][] board, String word) {
            if(board == null || board.length == 0) {
                return false;
            }
            
            if(word == null || word.length() == 0) {
                return true;
            }
            
            boolean result = false;
            
            for(int i = 0; i < board.length; i++) {
                for(int j = 0; j < board[0].length; j++) {
                    if(word.charAt(0) == board[i][j]) {
                       result = DFS(board, word, 0, i, j); 
                       //might start from more than one positions, but once a solution if found, return true immediately
                       if(result) {
                           return result;
                       }
                    }
                }
            }
            return result;
        }
        
        public boolean DFS(char[][] board, String word, int k, int i, int j) {
            if(k == word.length()) {
                return true;
            }
            
            if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
                return false;
            }
            
            if(board[i][j] != word.charAt(k)) {
                return false;
            }
    
            board[i][j] = '#'; //mark the position
            
            boolean result = DFS(board, word, k + 1, i + 1, j) 
                    || DFS(board, word, k + 1, i - 1, j)
                    || DFS(board, word, k + 1, i, j + 1)
                    || DFS(board, word, k + 1, i, j - 1);
                    
            board[i][j] = word.charAt(k); //restore the char in the board, might be used in next search
    
            return result;
        }
    }
    

Log in to reply
 

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