Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example, Given board=

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word="ABCCED", - > returns true

Solution: DFS下一层前，记得先把当前格子改为特殊字符，否则会死循环，recursion返回后把当前格子backtracking到原来的字符。

    boolean found = false;
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                search(word, 0, board, i, j);
                if (found) {
                    return true;
                }
            }
        }
        return false;
    }
    private void search(String word, int index, char[][] board, int x, int y) {
        if (found || index >= word.length()) {
            return;
        }
        if (board[x][y] == word.charAt(index)) {
            if (index == word.length() - 1) {
                found = true;
                return;
            }
            char temp = board[x][y];
            board[x][y] = '.';
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length || board[nx][ny] == '.') {
                    continue;
                }                
                search(word, index + 1, board, nx, ny);
            }
            board[x][y] = temp;
        }
    }

.或者写为：

    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0){
            return false;
        }
        if(word.length() == 0){
            return true;
        }

        for(int i = 0; i < board.length; i++){

            for(int j = 0; j < board[i].length; j++){
                if(find(i, j, board, word, 0)){
                    return true;
                }

            }
        }
        return false;
    }

    private boolean find(int i, int j, char[][] board, String word, int start){
        if(start == word.length()){
            return true;
        }
        if(i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] != word.charAt(start)){
            return false;
        }

        board[i][j] = '#'; //important

        boolean next = find(i + 1, j, board, word, start + 1) || find(i - 1, j, board, word, start + 1)
                       || find(i, j + 1, board, word, start + 1) || find(i, j - 1, board, word, start + 1);

        board[i][j] = word.charAt(start); //important

        return next;
    }