原文地址：https://www.cnblogs.com/ryuo-ou/p/19837741 同步说明：该文已完整同步到站内博客，便于统一检索和阅读。
在图论和字符串算法交叉的领域，有一道著名的难题叫做 “单词搜索 II”（LeetCode 212）。给定一个二维字符网格 board 和一个单词列表 words，我们的任务是找出矩阵中所有能够连通构造出来的单词（且每次字母只能由相邻方块上下左右产生）。
这道题是考察开发者的 Backtracking (回溯算法) 加上 Trie (字典树/前缀树) 高级融合的巅峰之作。今天我们就结合上面的这套 Go 语言源码，将这道题掰开了揉碎了讲讲其中的算法机制和令人拍案叫绝的底层代码细节。
一、 为什么单用回溯/DFS 会超时？我们要这棵“树”干什么？
普通的单词搜索：给定矩阵和一个字符串 "apple" 去找，你可以愉快地从网格的一个 a 开始通过四向做 DFS，如果找对就返回。
但在此题中，我们需要找的是 多个散落的字符串单词：["oath", "pea", "eat", "rain"]
假如说你要把他们排着队，一个接着一个地用 DFS 在整个迷宫里找一遍，这无疑是冗长极度的 \(O(N \times \text{迷宫大小})\) 浪费。
破局点在：前缀过滤（Trie Tree）。
我们可以反向思维，把待查询的所有字典词汇整合成一棵有层次的 Prefix Tree（字典树）。然后让整个矩阵像吃自助餐一样，对网格每一个单元格发起四面八方的探索，并在树上“照镜子”。只要：
- 这个脚印连出来的字符串已经在字典树分岔里走没路了（即
nil），我们就立刻拔断网格这条错误的蔓延根（DFS 剪枝），而不需要非得到撞穿南墙！ - 将成百上千次“单词到底能不能存在”的判断，完美折叠在了单词树深度相同的时间中。
二、 代码设计中的三大细节（神来之笔）
看完了大方向，接下来我们来扒一下代码实现中那些看似不经意却蕴含无穷巧思的小细节：
细节 1：抛弃布尔 isEnd 标志，直接在叶子结点埋下单词真身
平常写 Trie ，往往会在节点末端声明一个结尾： isWord bool 等于 true 时，判断成词。
但这里并没有。请看我们是怎么改造普通节点的：
type TrieNode struct { children [26]*TrieNode word string // 这是整套代码中最精巧的设计点之一
}
如果在叶子节点存储 true，你在二维网格中用 DFS 回溯游走的时候，为了最终能交货输出单词，DFS 的函数签名里就必须全程夹带传递一个诸如 pathString 的追踪状态量，一路累加字符 a + p + p + l + e。但在 Go 中这种递归层面的字符串高频反复拼接开销是极其恐怖的。
我们的“高级操作”是：当你最终匹配到一棵树枝尽头时，它本来就是代表着一个完整的单词！ 所以我们在一开始构造插入字典的时候，就直接把整个单词字符串贴在这片树叶节点上。当 DFS 摸到了某个 cur.word != "" 时，当场缴获成果，无需维护任何传递轨迹！
细节 2：利用 '#' 符号掩盖足印（原地备忘录优化）
在标准的图的遍历（DFS）中，总是需要申请一个大小也为 \(M \times N\) 的巨大布尔棋盘 visited[i][j]，防止一个单词里的同个游标来回相互往返吃（如 \(A \rightarrow B\) 马上又弹回 \(A\) 形成了 \(A \rightarrow B \rightarrow A\)）。
但在这里的代码：
board[x][y] = '#' // (1) 把棋盘原格标黑
// ...经过向四周（上下左右）各种探索递归...
board[x][y] = ch // (2) 探索跑完后，把刚才那块格子擦干净，恢复原样字符
原因为何？ 一次极客级别的原地变量重写（In-place Modification）。
我们暂且借用原盘矩阵，将当前这行这列被占用过的字母替换成永远不会在字母字典中出现的井号 '#'（任何越界的 DFS 或是企图反复踩格子的行为都会在 board[nx][ny] != '#' 拦截住）。待到回溯结束返回上一层时，在将之前临时藏在局部遍历的原本字符 ch 还给网格。
这就白拿了 O(1) 的超少栈外空间。
细节 3：必须使用去重的哈希表承装结果
vis := map[string]bool{} //...
if cur.word != "" { vis[cur.word] = true
}
在矩阵中，有没有可能：一个巨大的板子上同时存在左上角能拼出 "dog"，右下角兜了一个圈子也能拼出 "dog"？当然有。在迷宫 DFS 的疯狂搜索中它是必然会碰到所有组合的。
如果不加上哈希表的收纳网袋以键值对去重，同一个字母单词可能会被这颗贪婪的检索书吞下两三次返回，从而引发 LeetCode 重复结果报错。
三、 结语
字典树与回溯 DFS 的交织堪称结构之美：一个提供在海量状态空间下的精准前导指针判断，一个提供强力四面全开搜索并且知错就退的图网试探。
而通过“利用 # 在矩阵中占坑免二维 Visited”以及“在叶子结点上绑定完整字符串，省下繁重拼接工作”，这道地狱难度的搜索题硬生生被压缩成了一款代码逻辑分明、优美且内存消耗极低的满分模板。