剑指 Offer 12. 矩阵中的路径

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。



 

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
 

提示：

1 <= board.length <= 200
1 <= board[i].length <= 200
board 和 word 仅由大小写英文字母组成

img

思路

这套题明显是一个矩阵搜索的问题，深度优先遍历的算法，（迷宫的简化版）

首先还是迷宫的那一套解题思路

  1. 上下左右都进行递归
  2. 递归的终止条件
    1. 递归的边界条件
    2. 超过矩阵的范围
    3. 到了查找的word的次数（长度）
    4. 路径上的字符和word的不匹配
    5. 不能再一次寻找的过程中折返
  3. 回溯
    1. 走过的路径需要标记，放弃的路径需要还原

实现

DFS + 剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
private static class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        boolean[][] vis = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 每一次遍历都要从根节点重新开始，index要归零
                if (dfs(board, words, i, j, vis, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] words, int x, int y, boolean[][] vis, int index) {
        //x和y不能超出边界，寻找过程中不能折返
        if (x < 0 || x >= board.length || y <  0 || y >= board[0].length || vis[x][y]){
            return false;
            // 路径上的字符和word中的字符要匹配
        }else if (board[x][y] != words[index]){
            return false;
            // 达到了寻找word的次数，并且之前的路径都匹配到了，直接返回
        }else if (index == words.length - 1){
            return true;
        }
        vis[x][y] = true;
        boolean flag = dfs(board, words, x + 1, y, vis, index + 1) ||
            dfs(board, words, x - 1, y, vis, index + 1) ||
            dfs(board, words, x, y + 1, vis, index + 1) ||
            dfs(board, words, x, y - 1, vis, index + 1);
        vis[x][y] = false;
        return flag;
    }
}

复杂度分析：
M, N, 分别为矩阵行列大小， K 为字符串 word 长度。

时间复杂度：O（3^K * MN）

空间复杂度O（k + MN）

优化

可以优化上面的空间复杂度，上面的算法中额外申请了MN的二维矩阵，用于存储是否访问过节点，但是这个额外的空间可以不需要

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
private static class Solution {
        public boolean exist(char[][] board, String word) {
            char[] words = word.toCharArray();
            boolean[][] vis = new boolean[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    // 每一次遍历都要从根节点重新开始，index要归零
                    if (dfs(board, words, i, j, 0)) {
                        return true;
                    }
                }
            }
            return false;
        }

        private boolean dfs(char[][] board, char[] words, int x, int y, int index) {
            //x和y不能超出边界，寻找过程中不能折返 （这里在走过的路径上把字符全部制空，所以不定不能匹配走过的路径，达到了禁止折返的目的）,路径上的字符和word中的字符要匹配
            if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != words[index]) {
                return false;
                // 达到了寻找word的次数，并且之前的路径都匹配到了，直接返回
            } else if (index == words.length - 1) {
                return true;
            }
            // 走过的路径制空
            board[x][y] = '\0';
            boolean flag = dfs(board, words, x + 1, y, index + 1) ||
                    dfs(board, words, x - 1, y, index + 1) ||
                    dfs(board, words, x, y + 1, index + 1) ||
                    dfs(board, words, x, y - 1, index + 1);
            // 这里也没有用额外的变量保存board[x][y]的值，而是直接用words[index]的值，因为只有前面的路径都匹配，才能走到这一步，所以这个值相当于保存在words中
            board[x][y] = words[index];
            return flag;
        }
    }

博客首先发布于：

https://lvxiaoyi.top/