单词搜索 II

最直接的想法：对 words 里每个单词，都从网格各处单独做一遍 DFS。可单词之间往往共享前缀，比如 oath 和 oak 都以 o-a 开头，这段路你会一搜再搜，白白重复。

换个思路：先把所有单词塞进一棵字典树 Trie，共享的前缀就只存一份。然后网格只 DFS 一遍，手里攥着 Trie 的当前节点同步往下走。当前格的字母在 Trie 里没有分支，就立刻剪掉，连试都不试。

灵魂帧 0 · 先把单词建成 Trie：先把四个单词建成这棵 Trie。从根往右每走一条边添一个字母，带勾的节点表示一个单词到此结束。接下来网格 DFS 时，我手里会一直攥着 Trie 上的一个节点，走到哪个字母就往那条边下沉。

灵魂帧 1 · 起点 (0,0)=o，Trie 根有 o 边：外层双循环让每个格子都当一次起点。先从左上角 (0,0)=o 出发。看 Trie 根：有没有 o 这条边？有。于是攥住 o 节点，把 (0,0) 标成走过，继续往四周探。

灵魂帧 2 · 把 (0,0) 标记，探到右邻 (0,1)=a：进入 (0,0) 后先把它原地改成星号占住，这样这条路径上不会重复用它。再看四个方向，右边 (0,1)=a。问当前 Trie 节点 o：有 a 这条边吗？有。攥住 a 节点，推进到 (0,1)，路径变成 o-a。

灵魂帧 3 · 从 (0,1) 往下到 (1,1)=t：在 (0,1)=a 处把它也占住，看四周。下方 (1,1)=t。当前 Trie 节点 a 有没有 t 边？有。推进到 (1,1)，路径变成 o-a-t。递归栈现在压了三层，每层都记着自己攥的 Trie 节点。

灵魂帧 4 · 走到 (2,1)=h，命中 oath！：在 (1,1)=t 处往下走到 (2,1)=h。当前 Trie 节点 t 有 h 边，而且这个 h 节点带勾——表示单词 oath 在此结束。立刻把 oath 收进答案，并把这个勾摘掉防止重复收。已找到单词 +1。

灵魂帧 5 · oath 这支回溯，格子全部还原：oath 之后的 h 节点没有更多分支，这条路探到头。于是逐层返回，每弹出一层就把那一格的星号改回原来的字母——这就是回溯，把网格恢复原样，好让别的起点重新使用这些格子。

灵魂帧 6 · 剪枝：起点 (0,3)=n，根没有 n 边：这就是 Trie 剪枝的威力。轮到 (0,3)=n 当起点，问 Trie 根有没有 n 边？根的边只有 o、p、e、r，没有 n。于是这一格直接红牌返回，连它的四个邻居都不去看——所有以 n 开头的死路一刀全砍掉。

灵魂帧 7 · 换起点 (1,3)=e，沿 e 进 Trie：继续换起点。到 (1,3)=e，Trie 根有 e 边，攥住 e 节点。注意左上那个 e 在 (1,0)，它的邻居里没有 a，走不通；而 (1,3) 这个 e 右边和下边能接上 a-t，所以 eat 是从这里连出来的。

灵魂帧 8 · (1,3)→(1,2)=a，前缀 ea：从 (1,3)=e 往左到 (1,2)=a。当前 Trie 节点 e 有 a 边，推进，路径 e-a。两格都被星号占住，递归栈两层。

灵魂帧 9 · (1,2)→(1,1)=t，命中 eat！：从 (1,2)=a 往左到 (1,1)=t。当前 Trie 节点 a 有 t 边，且这个 t 带勾——单词 eat 结束！收下 eat，摘掉勾。已找到单词 +1，现在是 2 个：oath 和 eat。

灵魂帧 10 · 全部起点跑完，回溯归位，输出答案：继续把剩下的起点跑完。pea 因为网格里没有 p，rain 因为根没接上完整路径，都没命中。所有 DFS 回溯后网格恢复原样，最终答案就是高亮的两条路径连出的 oath 和 eat。

一句话记住：把单词建成 Trie，网格 DFS 时手里同步攥着 Trie 节点往下走，当前字母在 Trie 里没分支就立刻剪掉，命中带词节点就收下并摘标记。

雷区实演 · 不判已占格 → 绕回去多用一次字母：演示这个坑：搜 eat 时走到 (1,2)=a，如果邻居判断忘了排除星号，就会从 (1,2) 又跳回刚占住的 (1,3)=e。同一个 e 被用了两次，等于在网格里凭空造字母，可能连出根本不存在的单词。所以邻居必须同时不越界且不是星号。

边界三连 · 三个极端输入都不慌：三个边界都验一遍：前缀在 Trie 里断掉就直接剪空；单格网格只要那个字母自己成词就命中；同一个词哪怕有两条连法，靠摘词标记也只会被收一次。三种极端都有人管，放心下笔。

面试追问 1：面试官常先问这个。答案的关键词是：共享前缀、只搜一遍、前缀不存在立即剪枝。

面试追问 2：这是个加分细节：节点直接存单词，命中即取，省去回拼路径。

面试追问 3：想再快一点，就做叶子剪枝：收完的空叶子从 Trie 删掉，让后面的搜索更早碰壁。

这题学完别乱跳，去专题 /leetcode-animation/ds?k=trie 连刷同类题：先打牢 LC208 实现 Trie，再回看 LC79 单词搜索 I 体会单串 DFS，最后回到本题感受 Trie 批量剪枝的提速。卡住时问 AI 助教「我的 DFS 为什么没剪枝」。