Description

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.

Example:

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

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

解法

典型的DFS搜索题，以矩阵的每一个点为起点进行搜索，知道找到匹配项或者矩阵搜索完成，注意不能重复访问点，所以采用一个数组记录是否该点被访问过，还有回溯的写法，搜索完成后重新将点标记为未访问状态。

具体代码如下：

class Solution {
    int[] diri = {0, 0, 1, -1};
    int[] dirj = {1, -1, 0, 0};

    public boolean exist(char[][] board, String word) {
        if (board.length == 0) {
            return false;
        }
        int[][] visited = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                Boolean res = DFS(board, i, j, word, 0, visited);
                if (res == true) {
                    return true;
                }
            }
        }
        return false;
    }

    Boolean DFS(char[][] board, int i, int j, String word, int start, int[][] visited) {
        if (board[i][j] != word.charAt(start)) {
            return false;
        }
        if (start == word.length() - 1) {
            return true;
        }
        visited[i][j] = 1;
        for (int dir = 0; dir < 4; dir++) {
            int nexti = i + diri[dir];
            int nextj = j + dirj[dir];
            if (nexti >= 0 && nexti < board.length && nextj >= 0 && nextj < board[0].length && visited[nexti][nextj] == 0) {
                if (DFS(board, nexti, nextj, word, start + 1, visited)) {
                    return true;
                }
            }
        }
        visited[i][j] = 0;
        return false;
    }
}