剑指Offer 12: 矩阵中的路径

[songyy5517]

给定一个 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

分析 典型的回溯问题，可以考虑使用DFS & 剪枝解决。

[songyy5517]

思路：回溯 & DFS & 剪枝

1. 异常处理；
2. 循环遍历矩阵，对矩阵中的每次字符进行路径判断；
3. 若存在一条路径，则直接返回true；
4. 循环结束未找到路径，则返回false。

路径判断函数：回溯 & DFS & 剪枝

1. 递归出口：
   • 若路径中的字符全部匹配完成，则返回true；
   • 匹配失败的情况下，返回false：（剪枝；2/3可合并） （1）字符越界； （2）字符已被访问； （3）字符不相等；
2. 将字符置于被访问状态；
3. DFS判断当前字符下是否存在可匹配的路径；
4. 匹配完成之后，将当前字符置为未访问状态；（回溯）
5. 返回匹配结果。

复杂度分析

• 时间复杂度： $O(M N 3^L)$ ， $M, N, L$ 分别表示矩阵的行数、列数和目标字符串长度，矩阵中每个字符都可作为起点，且对于一个字符，之后可能的方向选择最多有3种。
• 空间复杂度： $O(L)$ ，最坏情况下，递归深度为 $L$ ，需要占用 $O(L)$ 大小的栈空间。

[songyy5517]

class Solution {
    public boolean exist(char[][] board, String word) {
        // 思路：回溯问题，用DFS和剪枝解决
        // 1. 异常处理
        if (board == null || board[0].length == 0)
            return false;

        // 2. 遍历矩阵
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                if (checkPath(board, word, 0, i, j)){
                    return true;
                }
            }
        }

        return false;
    }

    boolean checkPath(char[][] board, String word, int path_len, int i, int j){
        // 1. 递归出口
        if (path_len == word.length())
            return true;

        // 剪枝
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || word.charAt(path_len) != board[i][j])
            return false;

        // 2. 将元素置为访问
        board[i][j] = '\0';

        // 3. DFS
        boolean flag = checkPath(board, word, path_len+1, i-1, j) ||
                checkPath(board, word, path_len+1, i+1, j) ||
                checkPath(board, word, path_len+1, i, j-1) ||
                checkPath(board, word, path_len+1, i, j+1);

        // 3. 回溯
        board[i][j] = word.charAt(path_len);

        return flag;
    }
}

[songyy5517]

2023/1/16

1. 在主函数中调用递归匹配函数时，需要考虑各种情况（矩阵总存在相同的元素，前面元素在路径上，后面的不在）
2. 递归出口需要讲匹配成功的情况置顶
3. 不能忽略回溯操作

2023/9/14

1. 可以将访问矩阵简化成字符串的赋值

2023/10/2

1. 可以问一个关于异常情况的问题；
2. 实现回溯的方式：将访问过的字符改成'\0'，范访问结束后改回原来的字符；
3. len++ ≠ len + 1

2023/11/7

1. 在递归出口中，要先判断是否数组越界，然后判断字符是否相等。如果顺序反过来，当数组越界时，会出现越界错误。

2024/4/17