Word Search

DFS.

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[][] used = 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 (helper(board, used, word, 0, i, j)) return true;
            }
        }
        return false;
    }
    
    public boolean helper(char[][] board, boolean[][] used, String word, int validNum, int i, int j){
        if (validNum == word.length()) return true;
        
        if ( board[i][j] == word.charAt(validNum) && used[i][j] == false){
            validNum++;
            used[i][j] = true;
            boolean a = (validNum == word.length());
            if (i-1 >= 0){
                a |=  helper(board, used, word, validNum, i-1, j);
            }
            if (i+1 < board.length){
                 a |=  helper(board, used, word, validNum, i+1, j);
            }
            if (j-1 >= 0){
                 a |=  helper(board, used, word, validNum, i, j-1);
            }
            if (j+1 < board[0].length){
                 a |=  helper(board, used, word, validNum, i, j+1);
            }
            if (a == false){
                validNum --;
                used[i][j] = false;
            }
            return a;
        }
        return false;
    }
}