矩阵中的路径 - JZ65

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。

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

示例：

输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出: true

输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出: true

输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出: false

解题思路

这是一道典型的回溯算法问题：

核心思想：

遍历矩阵中的每个位置作为起点
使用深度优先搜索(DFS)和回溯找路径
标记已访问的位置，避免重复使用
如果路径不通，回溯并取消标记

算法步骤：

遍历矩阵每个位置 (i, j)
如果 board[i][j] == word[0]，开始DFS搜索
DFS过程中：
- 标记当前位置为已访问
- 检查上下左右四个方向
- 递归搜索下一个字符
- 如果失败，回溯并取消标记
找到完整路径返回true

关键点：

如何标记已访问的位置？
回溯时如何恢复状态？
边界条件的处理

项目结构

.
├── go.mod              # Go 模块定义
├── types.go            # 工具函数和数据结构定义
├── solution.go         # 算法实现（你需要完成这个文件）
├── answer.go           # 参考答案（练习后查看）
├── solution_test.go    # 单元测试
└── README.md          # 说明文档

使用方法

1. 实现算法

在 solution.go 文件中实现：

exist(board [][]byte, word string) bool - 主要实现
existDFS(board [][]byte, word string) bool - DFS版本
existBFS(board [][]byte, word string) bool - BFS版本（挑战）

2. 运行测试

go test -v
go test -bench=.

时间和空间复杂度分析

方法	时间复杂度	空间复杂度	说明
DFS回溯	O(M×N×4^L)	O(L)	M×N网格，L单词长度，每个位置最多4个方向
BFS	O(M×N×4^L)	O(M×N×L)	需要存储路径状态

知识点

深度优先搜索(DFS)
回溯算法
矩阵遍历
状态标记与恢复
递归与迭代
广度优先搜索(BFS)应用

题目描述​

解题思路​

项目结构​

使用方法​

1. 实现算法​

2. 运行测试​

时间和空间复杂度分析​

知识点​