LeetCode 剑指 Offer 12. 矩阵中的路径

2023-11-23 HGNULB 约 5 分钟

文章信息 12 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节跳动阿里巴巴快手猿辅导百度剑指 Offer 剑指 Offer（第 2 版）

题目描述

✅ 剑指 Offer 12. 矩阵中的路径

题意分析

输入是一个字符矩阵和一个单词，输出一个布尔值：矩阵中是否存在一条路径，把路径上的字符按经过顺序连起来恰好等于这个单词。

有三条约束需要读准。第一，相邻只包括上下左右四个方向，不含对角线。第二，同一个格子在同一条路径里最多用一次，但不同的路径之间互不影响——某个格子在这次尝试中用过并不代表它以后不能再用。第三，路径的起点和终点没有任何限制，矩阵里任何一个格子都可能是起点。

题目只问「存在与否」，不问有多少条、也不问是哪一条，这说明一旦找到就可以立刻层层返回，不必把所有可能性跑完。这个信号决定了整份代码的返回值类型和剪枝写法。

需要单独想清楚的边界：单词长度为 1 时不需要走任何一步，只要矩阵里有这个字符就成立；单词比矩阵格子总数还长时必然不成立；矩阵中同一个字符大量重复时，同一个起点会衍生出很多条前缀相同的路径；以及走到矩阵四条边上时，越界判断必须先于取值。

「同一格不能重复使用」是本题唯一的记忆性状态，它既不能省，也不能做成全局的一次性标记，否则就变成了「整个矩阵每格只用一次」，这是完全不同的题。

解法：DFS 回溯搜索路径

核心思路

路径起点不固定，因此从每个格子尝试深度优先搜索。递归状态由当前位置 (row, col) 和待匹配字符下标 index 组成；只有当前位置字符匹配时，才继续搜索上下左右四个方向。

同一条路径不能重复使用格子。代码把当前字符临时改成题目字符集之外的 '#'，递归结束后再恢复，这就是回溯的“选择—搜索—撤销”。递归不变量是：进入下一层时，前 index 个字符已经由一条合法且无重复格子的路径匹配完成。

当所有字符都匹配时立即返回。成功分支也要恢复矩阵，避免函数对调用方留下副作用。

解题步骤

若单词长度超过矩阵格子数，直接返回 false。

枚举每个格子作为起点，调用 DFS 匹配单词第一个字符。

DFS 先检查越界和字符是否匹配；当前字符是最后一个时返回 true。

临时标记当前格子，递归搜索四个相邻方向的下一个字符。

恢复当前格子，并返回四个方向中是否有一个成功。

例如样例中的 ABCCED 可沿 (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,1) 匹配完成。

代码实现

class Solution {
    public boolean exist(char[][] board, String word) {
        if (word.length() > board.length * board[0].length) {
            return false;
        }
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                if (dfs(board, word, row, col, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int row, int col, int index) {
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length
                || board[row][col] != word.charAt(index)) {
            return false;
        }
        if (index == word.length() - 1) {
            return true;
        }

        char saved = board[row][col];
        board[row][col] = '#';
        boolean found = dfs(board, word, row + 1, col, index + 1)
                || dfs(board, word, row - 1, col, index + 1)
                || dfs(board, word, row, col + 1, index + 1)
                || dfs(board, word, row, col - 1, index + 1);
        board[row][col] = saved;
        return found;
    }
}

func exist(board [][]byte, word string) bool {
    if len(word) > len(board)*len(board[0]) {
        return false
    }
    for row := range board {
        for col := range board[0] {
            if wordDFS(board, word, row, col, 0) {
                return true
            }
        }
    }
    return false
}

func wordDFS(board [][]byte, word string, row int, col int, index int) bool {
    if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) ||
        board[row][col] != word[index] {
        return false
    }
    if index == len(word)-1 {
        return true
    }

    saved := board[row][col]
    board[row][col] = '#'
    found := wordDFS(board, word, row+1, col, index+1) ||
        wordDFS(board, word, row-1, col, index+1) ||
        wordDFS(board, word, row, col+1, index+1) ||
        wordDFS(board, word, row, col-1, index+1)
    board[row][col] = saved
    return found
}

复杂度分析

时间复杂度：$O(mn\cdot3^L)$，其中 $L$ 是单词长度。每个格子都可能作为起点；除第一步外，来路已被标记，每层至多继续三个方向。

空间复杂度：$O(L)$，来自递归栈；原地标记没有额外的访问数组。

关键点总结

搜索状态必须同时包含坐标、已匹配长度和当前路径的占用信息。

字符不匹配立即返回，是搜索最有效的剪枝。

标记只对当前路径生效，递归结束后必须恢复，兄弟分支才能继续使用该格子。

找到答案后用逻辑短路立即返回，不需要遍历剩余搜索树。

易错点总结

越界判断必须先于访问矩阵，否则边界递归会直接抛异常。

忘记撤销标记，会让失败路径污染其他起点或兄弟分支。

成功条件必须在当前字符匹配后判断，不能只看 index。

原地标记应使用输入中不可能出现的字符，并在成功和失败路径上都恢复。

相似题目

题目	难度	考察点
79. 单词搜索	中等	同构原题的网格回溯模板
212. 单词搜索 II	困难	字典树剪枝的多词搜索
980. 不同路径 III	困难	全覆盖路径计数
1219. 黄金矿工	中等	路径权值最大化