79. 单词搜索 (回溯)

class Solution {
    // 二维数组长
    int n;
    // 宽
    int m;
    // 字符串长度
    int len;
    // 将字符串转换成字符数组
    char[] letters;
    // 二维数组元素是否被访问过
    boolean[][] visited;
    char[][] board;
    public boolean exist(char[][] board, String word) {
        this.n = board.length;
        this.m = board[0].length;
        this.len = word.length();
        this.board = board;
        // 初始化布尔值
        this.visited = new boolean[n][m];
        this.letters = word.toCharArray();
        // 遍历二维数组所有元素
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                // 每个元素都要递归
                boolean res = search(i,j,0);
                if(res) return true;
            }
        }
        // 找不齐元素返回false
        return false;
    }
    // 回溯方法
    public boolean search(int i,int j,int k){
        // 字符数组的下标大于等于字符串长度,返回true
        if(k >= len) return true;
        // 当行坐标或列坐标越界,或字符数组当前状态不相等或二维数组中当前元素被访问过,返回false,属于剪枝
        if(i < 0 || j < 0 || i >=n || j >= m || letters[k] != board[i][j] || visited[i][j]) return false;
        // 当前轮访问过的元素标记为true
        visited[i][j] = true;
        // 每个元素按上下左右四个方向回溯,记录结果的布尔值
        boolean res = search(i + 1,j,k + 1) || search(i,j + 1,k + 1) || search(i - 1,j,k + 1) || search(i,j - 1,k + 1);
        // 当前元素的当前轮二维数组中所有元素遍历完后,将当前元素重新置为false,避免影响下一个元素在遍历数组时回溯时的检查
        visited[i][j] = false;
        return res;
    }
}