教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文是「算法通关手册」AlgoNote中 LeetCode 0079「单词搜索」的完整题解。这道题是回溯算法在二维矩阵数组 矩阵场景下的经典应用要求判断给定单词能否由网格中相邻单元格按顺序拼接而成。读完本文你将掌握「选择—递归—回溯」回溯框架在网格搜索问题中的落地写法、visited去重数组的设计要点以及如何将解法平滑升级到 LeetCode 0212「单词搜索 II」字典树 DFS 版本。本题同时收录于本书的回溯算法练习题目与高频面试 200 题清单中是面试中回溯 DFS 的高频考点。题目信息题目编号0079 单词搜索Word Search标签数组、字符串、回溯、矩阵、深度优先搜索难度中等题目链接0079. 单词搜索 - 力扣题目大意描述给定一个 $m \times n$ 大小的二维字符矩阵board和一个字符串单词word。要求如果word存在于网格中返回True否则返回False。说明单词必须按照字母顺序通过上下左右相邻的单元格字母构成且同一个单元格内的字母不允许被重复使用。$m board.length$。$n board[i].length$。$1 \le m, n \le 6$。$1 \le word.length \le 15$。board和word仅由大小写英文字母组成。示例示例 1输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCCED 输出true示例 2输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word SEE 输出true从示例 2 可以看出单词的路径允许「折线」行走S → E → E并不在同一直线上这正对应了四个方向都可递归搜索的要求。解题思路回溯算法核心思想本题可以看作一次带约束的深度优先搜索DFS从矩阵中的任意一个格子出发每一步选择上下左右四个方向中尚未访问过的相邻格子逐步匹配word的字符序列。一旦某条路径无法匹配后续字符走不通就撤销当前位置的访问标记并回退换一个方向继续尝试——这正是本书回溯算法章节中「走不通就退回换条路再试」思想的直接体现。设函数backtrack(i, j, index)表示从board[i][j]出发能否搜索到单词字母word[index]以及index位置之后的后缀子串。能搜索到则返回True否则返回False。backtrack(i, j, index)的执行步骤如下终止判断如果board[i][j] word[index]且index已经到达word字符串末尾则说明整条路径完整匹配返回True。递归深入如果board[i][j] word[index]且index尚未到达word末尾则遍历当前位置的四个相邻位置上、下、左、右。只要从某个相邻位置能继续搜索到后缀子串就返回True四个方向都试过仍无结果返回False。字符剪枝如果board[i][j] ! word[index]当前字符不匹配直接返回False不再向下探索。整个搜索过程可以视为一棵决策树每一层对应单词中的一位字符每个节点的四个分支对应「向上下左右哪个方向走」走到叶子匹配完整单词即命中走不通则回溯到上一层换分支。思路 1代码class Solution: def exist(self, board: List[List[str]], word: str) - bool: directs [(0, 1), (0, -1), (1, 0), (-1, 0)] rows len(board) if rows 0: return False cols len(board[0]) visited [[False for _ in range(cols)] for _ in range(rows)] def backtrack(i, j, index): if index len(word) - 1: return board[i][j] word[index] if board[i][j] word[index]: visited[i][j] True for direct in directs: new_i i direct[0] new_j j direct[1] if 0 new_i rows and 0 new_j cols and visited[new_i][new_j] False: if backtrack(new_i, new_j, index 1): return True visited[i][j] False return False for i in range(rows): for j in range(cols): if backtrack(i, j, 0): return True return False代码逐段拆解方向数组directs[(0, 1), (0, -1), (1, 0), (-1, 0)]分别表示右、左、下、上四个方向。通过new_i i direct[0]、new_j j direct[1]统一表达四个方向的偏移避免手写四段重复逻辑。visited去重数组由于「同一个单元格内的字母不允许被重复使用」用与board同尺寸的布尔矩阵记录当前递归路径上已访问的格子防止路径绕回自己。它是回溯过程中「状态」的核心载体。递归入口判定index len(word) - 1表示当前已匹配到单词的最后一个字符此时只需比较board[i][j] word[index]即可无需再访问邻居。做选择与撤销选择匹配成功时先将visited[i][j] True占用格子递归返回后若四条分支全部失败再执行visited[i][j] False释放格子。这正是回溯模板中「做选择 → 递归 → 撤销选择」三件套。边界剪枝0 new_i rows and 0 new_j cols保证不会越界访问矩阵。全局启动搜索遍历board的每一个格子将其作为起点调用backtrack(i, j, 0)一旦某个起点找到完整路径立即返回True。只有所有起点都失败才返回False。对照本书回溯算法章节归纳的通用模板def backtrack(参数): if 终止条件: 处理结果 return for 选择 in 可选列表: if 满足约束: 做选择 backtrack(新参数) 撤销选择可以清晰看出映射关系终止条件是「index到达word末尾」可选列表是「四个相邻方向」约束条件是「不越界 未被访问」做选择 / 撤销选择对应visited[i][j] True / False。掌握这个模板后可以顺带迁移到本书其他回溯经典题如全排列、子集、N 皇后。思路 1复杂度分析时间复杂度$O(m \times n \times 2^l)$其中 $m$、$n$ 为二维矩阵board的行数和列数$l$ 为字符串word的长度。最坏情况下每个格子都要作为起点尝试搜索而在单词匹配过程中每个位置最多有 3 个可用的新方向减去回溯回来的方向整体呈指数级搜索空间。空间复杂度$O(m \times n)$。其中visited数组占用 $O(m \times n)$递归栈深度最深不超过单词长度 $l$受 $l \le 15$ 约束。数据范围 $1 \le m, n \le 6$、$1 \le word.length \le 15$ 是回溯算法可行的前提指数级的时间复杂度只有在矩阵和单词规模都很小时才可接受。从深度优先搜索的视角再看本题单词搜索本质上是把二维矩阵当作一张图在图上做带约束的深度优先搜索。本书深度优先搜索章节指出DFS 的核心是「沿一条路径尽可能深入遇到无法继续的节点再回溯到上一个分叉点」。本题中每个单元格就是图中的一个节点上下左右相邻的单元格构成边word的字符序列就是目标路径的「形状约束」。与通用 DFS 遍历不同单词搜索有两个特殊之处起点不固定需要枚举矩阵中所有格子作为搜索起点外层双层循环的由来路径即答案不追求遍历完整张图只要找到一条与word完全吻合的路径就立即返回。理解了这一点就能明白backtrack返回值True/False的设计它向上一层传递「这条分支是否通向完整匹配」一旦某层返回True整个递归链立即收敛并返回True。进阶延伸单词搜索 II字典树 DFS单词搜索还有一道著名的进阶题目——0212. 单词搜索 II难度困难其完整题解同样收录在本书docs/solutions/0200-0299/目录下。区别在于0079 单词搜索给定一个单词用回溯搜索即可。0212 单词搜索 II给定一个单词列表要在网格中找到所有出现在列表中的单词。若对每个单词单独跑一遍回溯复杂度会很高因此题解采用「字典树Trie DFS」先把所有单词插入字典树再在网格上做 DFS沿途用字典树判断当前路径是某单词、某单词前缀还是无意义路径——是前缀则继续搜索否则立即剪枝停止。该解法还把「避免重复使用单元格」的方式从visited数组换成了「临时把当前格子改写为特殊字符#DFS 返回后再恢复」是一种值得学习的空间优化技巧。可以说先吃透 0079 的「回溯 四方向搜索 去重」基础框架再阅读 0212 的字典树版本是系统掌握「网格类搜索问题」的一条高效学习路径。相关练习与仓库导航本题已被收录在本书全部题解索引中可在docs/solutions/0001-0099/word-search.md直接查看原始题解。回溯算法理论学习回溯算法详解含通用模板、全排列 / 子集 / N 皇后完整例题。深度优先搜索理论基础深度优先搜索含递归实现与显式栈实现。进阶题目0212. 单词搜索 II字典树 DFS。更多回溯类题目全排列、组合总和、子集、括号生成、复原 IP 地址、24 点游戏等见回溯算法题目列表。完整题目清单见题解列表高频面试题清单见面试 200 题列表。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 79 单词搜索Word Search题解二维网格上的 DFS 回溯算法实战LeetCode 79 单词搜索Word Search题解二维网格上的 DFS 回溯算法实战 本文基于 leetcode 题解仓库中的 79.word s文档教程知识库LeetCode 79 单词搜索Word Search题解二维网格中的回溯 DFS 实战LeetCode 79 单词搜索Word Search题解二维网格中的回溯 DFS 实战 本文以当前仓库 problems/79.word search.文档教程知识库LeetCode-Go 题解79. Word Search 二维网格单词搜索的 DFS 回溯法LeetCode Go 题解79. Word Search 二维网格单词搜索的 DFS 回溯法 导读 本文围绕 LeetCode 第 79 题 Word Se示例工程上一篇Folder Explorer 快速上手文件夹目录树导出与统计工具完整指南10 分钟跑起来下一篇Boring Notch 使用指南3 步把闲置的 MacBook 刘海变成实用控制中心创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考