12.矩阵中的路径 #

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                // 从第一个点开始比对
                if(dfs(board,words,i,j,0)) return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, char[] words,int i, int j, int k){
        // 边缘情况或者不相等，直接返回false
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || words[k] != board[i][j]) return false;
        // 如果已经到了最后一个字符且相等，返回true
        if(k == words.length - 1) return true;
        // 先清除当前字符，在下一轮比对该字符时会返回false
        board[i][j] = '\0';
        // 上下左右四个方向进行比较
        boolean res = dfs(board,words,i-1,j,k+1) || dfs(board,words,i+1,j,k+1) || dfs(board,words,i,j-1,k+1) || dfs(board,words,i,j+1,k+1);
        // 还原字符
        board[i][j] = words[k];
        // 返回结果
        return res;
    }
}