79. Word Search

Medium

看的答案，这种简单粗暴的DFS还是不会写. 抄过来又觉得很简单，多写几道多体会体会吧

class Solution {
    //DFS
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];        
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == word.charAt(0) && dfsHelper(board, word, i, j, 0, visited)){
                    return true;
                }        
            }
        } 
        return false;
    }
    
    private boolean dfsHelper(char[][] board, String word, int i, int j, int index, boolean[][] visited){
        if (index == word.length()){
            return true;
        }        
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)){
            return false;
        }
        visited[i][j] = true;
        if (dfsHelper(board, word, i + 1, j, index + 1, visited) || dfsHelper(board, word, i - 1, j, index + 1, visited) ||
           dfsHelper(board, word, i, j + 1, index + 1, visited) || dfsHelper(board, word, i, j - 1, index + 1, visited)){
            return true;
        }
        visited[i][j] = false;
        return false;
    }
}