[LC]12. 矩阵中的路径

🚩传送门：力扣题目
力扣题目

题目

给定一个 二维字符网格 和一个字符串单词 。如果存在于网格中，返回 ；否则，返回。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true

解题思路：DFS

本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS） 解决。

复杂度分析

时间复杂度： ，最差情况下，需要遍历矩阵中长度为 字符串的所有方案，其中 和 分别是矩阵的行数和列数。

空间复杂度： ，其中 为模式串长度，搜索过程中的递归深度不超过 。

我的代码

class Solution {
    public static boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;
        if (word == null || word.equals("")) return false;
        // 标记是否被访问
        boolean[][] view = new boolean[board.length][board[0].length];
        // 遍历每一个点做起始位置dfs
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                // 搜索到了匹配的
                if (dfs(board, word, i, j, view)) return true;
            }
        }
        // 搜索完毕所有可能未被访问
        return false;
    }
    private static boolean dfs(char[][] board, String word, int i, int j, boolean[][] view) {
        if (isvalid(board, i, j, view)) {
            // 判断是否相等
            if (board[i][j] != word.charAt(0)) return false;
            if(word.length()==1) return true;
            // 当前位置合法,先标记访问
            view[i][j] = true;
            // 定义4个方向,右下左上
            int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            for (int k = 0; k < dir.length; k++) {
                // 四个方向搜索,如果能搜索到就返回搜索到的结果
                if (dfs(board, word.substring(1), i + dir[k][0], j + dir[k][1], view))
                    return true;
            }
            // 四个方向搜索完毕,放弃当前点(i,j),置为未访问
            view[i][j] = false;
        }
        return false;
    }
    private static boolean isvalid(char[][] board, int i, int j, boolean[][] view) {
        // 越界非法
        if (i < 0 || i >= board.length) return false;
        if (j < 0 || j >= board[i].length) return false;
        // 已被访问,蛇撞身体了
        if (view[i][j]) return false;
        // 合法的点(i,j)
        return true;
    }
    public static void main(String[] args) {
        char[][] board=new char[][]{{'A','B'}};
        System.out.println(exist(board, "BA"));
    }
}

K 神代码

确实代码简化了很多

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;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        // 边界合法性判断
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if (k == word.length - 1) return true;
        // 通过修改board[i][j]达到访问标记的作用
        board[i][j] = '\0';
        // 四向搜索
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        // 取消访问标记,用word[k]恢复
        board[i][j] = word[k];
        return res;
    }
}