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

约 6 分钟
文章信息 12 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 剑指 Offer 剑指 Offer（第 2 版） 字节 阿里 百度 快手 猿辅导
标签
数组 字符串 矩阵 回溯

题目描述

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

image-20261001225023480

image-20260928195232133

image-20260928195232134

image-20260928195232135

题意分析

判断能否在字符矩阵中找到一条路径，按路径经过的顺序恰好组成 word。起点任意，每一步只能走到上下左右相邻格子，不能斜走。

同一个格子在同一条路径中最多使用一次，但一次尝试失败后可以重新用于其他路径。题目只问是否存在，不需要列出路径；矩阵和单词均非空，单词比格子总数更长时必定无解。

解法：DFS 回溯搜索路径

核心思路

[!blue]

枚举每个格子作为起点，递归状态 dfs(row, col, index) 表示尝试用当前格匹配 word[index]。进入这次调用时，前面的字符已经由路径中的其他格子匹配，它们处于临时占用状态。

先检查坐标是否合法，再检查当前格是否等于所需字符。不匹配就立即失败；匹配且已到单词最后一个字符时，整条路径完成，返回成功。

否则临时把当前格改成输入中不会出现的 '#'，再尝试四个相邻方向匹配下一个字符。被占用的格子无法再通过字符检查，因此搜索不会在同一条路径中重复使用它。

四个方向结束后恢复当前字符，再返回是否找到答案。访问标记只属于当前路径，不是全局访问记录；失败后不恢复，会错误地阻止兄弟分支和其他起点使用这个格子。成功时也先恢复，保证调用结束后输入矩阵保持原样。

外层枚举全部起点，内层枚举所有允许的相邻选择；剪掉的仅是越界、字符错误或重复用格的非法分支。因此任意合法路径都能被覆盖，找到一条后即可短路停止。

解题步骤

  1. 若单词长度超过格子数，返回 false。
  2. 枚举每个格子作为起点，从单词下标零开始 DFS。
  3. 每次调用先检查越界和字符，合法且匹配末字符时返回 true。
  4. 保存原字符，将当前格暂时标记为占用，再尝试四个方向。
  5. 将搜索结果保存在 found，恢复原字符，然后返回 found。
  6. 任一起点成功则返回 true；全部失败才返回 false。

代码实现

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)$，其中 $m,n$ 为矩阵行列数，$L$ 为单词长度。每个格子可能作为起点，第一步至多四个方向，后续至少不能走回已占用的来路，每层至多继续三个方向；字符匹配会进一步剪枝。
  • 空间复杂度：$O(L)$，用于递归栈；原地标记省去了额外访问数组。

关键点总结

[!green]

  • 搜索状态由位置、待匹配下标及当前路径的占用情况共同决定。
  • 标记禁止重复使用当前路径中的格子，恢复则允许不同路径独立尝试。
  • 短路减少后续搜索，统一恢复步骤保证成功和失败都不破坏输入。

易错点总结

[!yellow]

  • 访问字符之前必须完成越界判断，不能在条件顺序中先读取非法坐标。
  • 必须确认当前字符相等后才判断是否匹配到末尾，不能只凭下标就宣布成功。
  • 不能使用永久访问标记；同一个格子在不同路径中可以被重复尝试。
  • 原地标记必须选输入中不存在的字符，否则可能被误当成可匹配内容。
  • 直接从递归调用处返回成功，可能跳过当前层恢复；应先保存结果，再恢复并返回。

相似题目

题目 难度 关联与区别
212. 单词搜索 II 困难 从查找一个单词扩展为多个单词，Trie能共享相同搜索前缀。
200. 岛屿数量 中等 同样在网格上DFS，本题的访问标记只对当前路径有效，回溯时必须恢复。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/29904918
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！