79. 单词搜索

// LeetCode指定调用方法 
public boolean exist(char[][] board, String word) {
		
    int m = board.length;
    int n = board[0].length;

    boolean[][] flag = new boolean[m][n];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if(wordSearch(board, word, flag, i, j, 0)) {
                return true;
            }
        }
    }
    return false;

}

private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

// 在二维网格board中搜索word单词，a、b记录当前搜索位置，t记录当前已搜索到的单词字母数量
private boolean wordSearch(char[][] board, String word, boolean[][] flag, int a, int b, int t) {

    // 当单词字母全部被搜索到时，返回true
    if (word.length() == t) {
        return true;
    }

    // 当搜索到边界或者已被搜索过的位置或者该位置的字母不是word对应位置的字母时，返回false
    if (a < 0 || b < 0 || a >= board.length || b >= board[0].length || flag[a][b] || board[a][b] != word.charAt(t)) {
        return false;
    }

    // 标记已搜索到的位置
    flag[a][b] = true;

    for (int[] d : direction) {

        // 当单词已被搜索完时，不在继续搜索，停止递归回溯
        if (wordSearch(board, word, flag, a + d[0], b + d[1], t + 1)) {
            return true;
        }
    }

    // 复原标记
    flag[a][b] = false;

    return false;
}