word search.java

public class Solution {
    
    
    public boolean exist(char[][] board, String word) {
        int len = word.length();
        if(len == 0)
            return false;
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < cols; ++j){
                if(dfs(i, j, 0, word, board))//prune
                    return true;
            }
        }
        return false;
    }
    
    private boolean dfs(int i, int j, int index, String word, char[][] dict) {
        int rows = dict.length;
        int cols = dict[0].length;
        
        if(index == word.length()-1 && word.charAt(index)==dict[i][j]) 
            return true;  
         
        if(word.charAt(index) != dict[i][j])
            return false;
        
        char temp = dict[i][j];//do not need to create a boolean matrix
        dict[i][j] = '.';
        
        boolean b1 = false, b2 = false, b3 = false, b4 = false; 
        if(i - 1 >= 0 && dict[i - 1][j] != '.')
            b1 = dfs(i - 1, j, index + 1, word, dict);
        if(!b1 && i + 1 < rows && dict[i + 1][j] != '.')//prune
            b2 = dfs(i + 1, j, index + 1, word, dict);
        if(!b1 && !b2 && j - 1 >=0 && dict[i][j - 1] != '.')//prune
            b3 = dfs(i, j - 1, index + 1, word, dict);
        if(!b1 && !b2 && !b3 && j + 1 < cols && dict[i][j + 1] != '.')//prune
            b4 = dfs(i, j + 1, index + 1, word, dict);
        
        dict[i][j] = temp;
        
        return b1 || b2 || b3 || b4;
    }
}