LeetCode 212 单词搜索 II 深度解析从朴素回溯到 Trie 剪枝的三种解法leetcode1/leetcode 项目实战【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于 leetcode1/leetcode 仓库中的 search-for-word-ii.md 文档展开完整讲解 LeetCode 212「Word Search II」的三种递进式解法朴素回溯Backtracking、Trie 哈希集合、Trie 引用计数剪枝并结合仓库内 python/0212-word-search-ii.py、java/0212-word-search-ii.java、cpp/0212-word-search-ii.cpp 等 9 种语言源码印证实现细节。读完本文你将掌握二维网格 单词集合类问题的标准套路如何用 DFS 在网格中枚举路径、如何用 Trie 共享前缀搜索、以及如何用refs引用计数剪枝把性能推到极致。前置知识Prerequisites在动手解这道题之前需要先熟悉四个基础概念概念说明Backtracking回溯通过做出选择、递归探索、撤销选择来尝试所有可能的路径是穷举 复原的经典范式DFS深度优先搜索沿每条分支尽可能深入后再回溯用于遍历图或网格Trie前缀树一种树形数据结构用于高效的前缀匹配与单词存储让多个单词共享公共前缀2D Grid Traversal二维网格遍历在矩阵中沿上下左右四个方向移动同时处理越界边界这些概念在仓库中都有对应实现例如 implement-prefix-tree.md前缀树专题、search-for-word.md单词搜索版 Word Search I可作为递进阅读材料。而本仓库的 README.md 中 0212 一行的完成状态表显示该题在 C/C/C#/Go/Java/JavaScript/Kotlin/Python/Swift/TypeScript 等语言下均有通过实现。1. 解法一朴素回溯逐词搜索1.1 核心直觉对words中的每一个单词尝试在棋盘上描出它从匹配首字母的格子出发沿着上下左右相邻格子一步步走。为了不让同一个格子在一段单词路径中被重复使用临时把格子标记为已访问探索完成后再恢复——这正是经典回溯。如果某个单词的所有字符都能按顺序匹配上该单词就找到了加入结果集。1.2 算法步骤设ROWS、COLS为棋盘尺寸对words中每个word把每个格子(r, c)作为潜在起点仅当它匹配word[0]运行回溯函数backtrack(r, c, i)i 当前需要匹配的word下标基线条件i len(word)返回true整个单词已匹配若越界或棋盘格子不等于word[i]返回false将格子标记为已访问例如替换为*向 4 个邻居递归下标推进到i 1恢复原字符撤销选择返回是否存在某个邻居路径成功若任一起点成功把word加入答案并停止搜索该词。1.3 代码实现以下给出 Python / Java / C 三种代表实现仓库中 Go / Kotlin / Swift / Rust 版本可在本文末尾源码索引中找到class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: ROWS, COLS len(board), len(board[0]) res [] def backtrack(r, c, i): if i len(word): return True if (r 0 or c 0 or r ROWS or c COLS or board[r][c] ! word[i] ): return False board[r][c] * ret (backtrack(r 1, c, i 1) or backtrack(r - 1, c, i 1) or backtrack(r, c 1, i 1) or backtrack(r, c - 1, i 1)) board[r][c] word[i] return ret for word in words: flag False for r in range(ROWS): if flag: break for c in range(COLS): if board[r][c] ! word[0]: continue if backtrack(r, c, 0): res.append(word) flag True break return respublic class Solution { public ListString findWords(char[][] board, String[] words) { int ROWS board.length, COLS board[0].length; ListString res new ArrayList(); for (String word : words) { boolean flag false; for (int r 0; r ROWS !flag; r) { for (int c 0; c COLS; c) { if (board[r][c] ! word.charAt(0)) continue; if (backtrack(board, r, c, word, 0)) { res.add(word); flag true; break; } } } } return res; } private boolean backtrack(char[][] board, int r, int c, String word, int i) { if (i word.length()) return true; if (r 0 || c 0 || r board.length || c board[0].length || board[r][c] ! word.charAt(i)) return false; board[r][c] *; boolean ret backtrack(board, r 1, c, word, i 1) || backtrack(board, r - 1, c, word, i 1) || backtrack(board, r, c 1, word, i 1) || backtrack(board, r, c - 1, word, i 1); board[r][c] word.charAt(i); return ret; } }class Solution { public: vectorstring findWords(vectorvectorchar board, vectorstring words) { int ROWS board.size(), COLS board[0].size(); vectorstring res; for (string word : words) { bool flag false; for (int r 0; r ROWS !flag; r) { for (int c 0; c COLS; c) { if (board[r][c] ! word[0]) continue; if (backtrack(board, r, c, word, 0)) { res.push_back(word); flag true; break; } } } } return res; } private: bool backtrack(vectorvectorchar board, int r, int c, string word, int i) { if (i word.length()) return true; if (r 0 || c 0 || r board.size() || c board[0].size() || board[r][c] ! word[i]) return false; board[r][c] *; bool ret backtrack(board, r 1, c, word, i 1) || backtrack(board, r - 1, c, word, i 1) || backtrack(board, r, c 1, word, i 1) || backtrack(board, r, c - 1, word, i 1); board[r][c] word[i]; return ret; } };1.4 复杂度分析时间复杂度$O(w \times m \times n \times 4 \times 3^{t-1})$空间复杂度$O(t)$其中 $w$ 是单词个数$m$ 是行数$n$ 是列数$t$ 是words中最长单词的长度。为什么是 $4 \times 3^{t-1}$每次从当前格子出发第一步有 4 个方向可选进入路径后由于不能走回头路当前格子已被标记后续每一步最多只有 3 个有效方向。这种首步 4 选、其后 3 选的结构是网格回溯问题复杂度分析的核心。1.5 局限朴素回溯最大的浪费在于w个单词完全独立搜索彼此之间没有任何信息共享。若words [oath, oats, oak]三个单词共享前缀oa朴素回溯会为每个单词从零开始重新在棋盘上走一遍o - a的前缀路径重复劳动严重。这正是解法二引入 Trie 的动机。2. 解法二回溯 Trie 哈希集合2.1 核心直觉逐词搜索做了大量重复工作。Trie前缀树让这些工作得以共享在棋盘上行走时只继续那些匹配某个单词前缀的路径。于是棋盘 DFS 探索的是可能的前缀每当 Trie 节点表明此前缀是一个完整单词时就记录下来。同时为避免单条路径中重复使用同一格子需要在当前 DFS 路径中维护一个visited 集合返回时回溯/移除。2.2 算法步骤用所有words构建一棵 Trie每个 Trie 节点存储children下一层字母和isWord此处是否为某个单词的结尾初始化res为集合去重visit为当前 DFS 路径的访问集合定义dfs(r, c, node, wordSoFar)若(r, c)越界、已访问、或board[r][c]不在node.children中停止标记(r, c)为已访问移动 Trie 指针node node.children[board[r][c]]把当前字符追加到wordSoFar若node.isWord true把wordSoFar加入res用更新后的node和wordSoFar递归 4 个邻居上下左右回溯把(r, c)从visit中移除从每个格子(r, c)以 Trie 根节点为起点运行 DFS返回res中收集到的全部单词。2.3 代码实现Pythonclass TrieNode: def __init__(self): self.children {} self.isWord False def addWord(self, word): cur self for c in word: if c not in cur.children: cur.children[c] TrieNode() cur cur.children[c] cur.isWord True class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for w in words: root.addWord(w) ROWS, COLS len(board), len(board[0]) res, visit set(), set() def dfs(r, c, node, word): if (r 0 or c 0 or r ROWS or c COLS or (r, c) in visit or board[r][c] not in node.children ): return visit.add((r, c)) node node.children[board[r][c]] word board[r][c] if node.isWord: res.add(word) dfs(r 1, c, node, word) dfs(r - 1, c, node, word) dfs(r, c 1, node, word) dfs(r, c - 1, node, word) visit.remove((r, c)) for r in range(ROWS): for c in range(COLS): dfs(r, c, root, ) return list(res)Java 版本用boolean[][] visit二维数组代替哈希集合java/0212-word-search-ii.java 中为HashSetString存坐标字符串C 版本同样用vectorvectorboolGo 版本用map[[2]int]bool。三种做法在语义上完全等价只是去重/标记的数据结构不同。2.4 复杂度分析时间复杂度$O(m \times n \times 4 \times 3^{t-1} s)$空间复杂度$O(s)$其中 $m$ 是行数$n$ 是列数$t$ 是最长单词长度$s$ 是所有单词长度之和即 Trie 的规模。与解法一相比搜索部分的时间上界从w倍降为 1 倍所有单词共享同一趟前缀 DFS但额外付出 $O(s)$ 的空间构建 Trie。2.5 两个值得注意的细节去重结果集用setPythonset/ JavaHashSet/ Gomap[string]bool因为棋盘上可能存在多条路径拼出同一个单词直接 append 会产生重复项字符串传递word board[r][c]采用不可变字符串逐层传递Python/JavaGo 版本同样用word string(char)而 Rust 版本rust/0212-word-search-ii.rs用word.push(ch) 回溯word.pop()复用同一可变缓冲区避免每层拷贝。3. 解法三回溯 Trie引用计数剪枝推荐3.1 核心直觉解法二仍会在已无剩余单词的分支上继续探索。解法三在 Trie 上引入激进剪枝每个 Trie 节点维护refs 字典中还有多少个单词经过该节点成功找到一个或多个单词后每个 DFS 调用向上返回它在当前前缀下新找到的单词数量随着 DFS 回溯从该路径上的每个 Trie 节点减去这个数量把已找到的单词从所有相关节点移除若某节点refs减到0说明该分支已死亡没有剩余单词用到它直接把父节点的指针切断prev.children[...] null让后续 DFS 永远不会再探索这些无用的前缀。此外不再使用独立的 visited 集合而是原地标记棋盘探索某条路径时临时把board[r][c]设为*回溯时恢复原字符。3.2 Trie 节点存储什么每个节点包含字段含义children[26]下一层字母定长数组比哈希表更快idx若此处是某单词结尾记录其在words中的下标否则为-1refs仍存活的、经过该节点的单词数量含在此结束的单词3.3 算法步骤构建 Trie插入每个words[i]插入过程中路径上的每个节点refs加 1结尾节点记录idx i从每个棋盘格子运行dfs(r, c, node)尝试用board[r][c]扩展当前 Trie 路径DFS 规则若越界、当前格子已是*路径内已用、或 Trie 中没有board[r][c]对应的子节点停止否则取字母ch board[r][c]移动到子节点child node.children[ch]标记格子board[r][c] *若child.idx ! -1找到单词把words[child.idx]加入结果置child.idx -1防重复初始化found 1向 4 个邻居以child递归累加返回数量到found令child.refs - found若child.refs 0切断该分支node.children[ch] null恢复棋盘格子返回found使每个祖先节点都能更新自己的refs每次顶层 DFS 结束后root.refs减去返回值返回收集到的结果。3.4 代码实现Pythonclass TrieNode: def __init__(self): self.children [None] * 26 self.idx -1 self.refs 0 def addWord(self, word, i): cur self cur.refs 1 for c in word: index ord(c) - ord(a) if not cur.children[index]: cur.children[index] TrieNode() cur cur.children[index] cur.refs 1 cur.idx i class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for i in range(len(words)): root.addWord(words[i], i) ROWS, COLS len(board), len(board[0]) res [] def getIndex(c): index ord(c) - ord(a) return index def dfs(r, c, node): if (r 0 or c 0 or r ROWS or c COLS or board[r][c] * or not node.children[getIndex(board[r][c])]): return 0 tmp board[r][c] board[r][c] * prev node node node.children[getIndex(tmp)] found 0 if node.idx ! -1: res.append(words[node.idx]) node.idx -1 found 1 found dfs(r 1, c, node) found dfs(r - 1, c, node) found dfs(r, c 1, c, node) if False else dfs(r, c 1, node) found dfs(r, c - 1, node) board[r][c] tmp node.refs - found if not node.refs: prev.children[getIndex(tmp)] None return found for r in range(ROWS): for c in range(COLS): root.refs - dfs(r, c, root) return res上例中dfs(r, c 1, node)的写法请以文档原文为准原文为dfs(r, c 1, node)。注意原始文档该解法为children定长数组26Java/C/C#/Go/Kotlin/Swift/Rust 版本均遵循c - a映射到数组下标的结构例如 cpp/0212-word-search-ii.cpp 中的children[26]与node-children[board[r][c] - a]。3.5 复杂度分析时间复杂度$O(m \times n \times 4 \times 3^{t-1} s)$空间复杂度$O(s)$其中 $m$ 是行数$n$ 是列数$t$ 是最长单词长度$s$ 是所有单词长度之和。虽然理论上界与解法二相同但refs剪枝让实际运行时间显著更优一旦某分支剩余单词数为 0物理切断指针后后续所有从其他起点发起的 DFS 都直接跳过该分支避免了对死前缀的重复探索。4. 三种解法对比总览维度解法一朴素回溯解法二Trie 哈希集合解法三Trie refs 剪枝是否共享前缀否逐词独立是是访问标记原地*独立 visited 集合原地*去重方式逐词只加一次结果集合setidx -1剪枝策略无无仅前缀匹配refs计数 断链时间上界$O(w \cdot m \cdot n \cdot 4 \cdot 3^{t-1})$$O(m \cdot n \cdot 4 \cdot 3^{t-1} s)$$O(m \cdot n \cdot 4 \cdot 3^{t-1} s)$空间上界$O(t)$$O(s)$$O(s)$实战性能最差重复前缀搜索中等最优死分支被物理剪除解法三既是面试中的加分答案也是仓库中各语言实现的主流形态。5. 常见陷阱与规避Common Pitfalls5.1 忘记对结果去重棋盘上多条路径可能拼出同一个单词直接加入结果列表会产生重复项。规避方式有两种结果用集合set存储在 Trie 中标记单词已被找到把结尾节点的idx置为-1解法三或把isWord/word置空解法二变体。例如仓库 javascript/0212-word-search-ii.js 中checkWord找到单词后执行node.word 正是标记已找到的写法python/0212-word-search-ii.py 则同时用node.isWord False与res集合双重保险。5.2 回溯后没有恢复棋盘直接在棋盘上标记如board[r][c] *后若递归结束忘记恢复原字符棋盘状态被破坏其他起点或其他单词将无法找到有效路径。正确做法是保存tmp board[r][c]在递归返回后恢复。5.3 构建了 Trie 却不剪枝建好 Trie 但找到单词后不剪枝会导致持续探索死分支没有递减refs、没有在refs归零时删除节点算法就会继续搜索不可能产生新单词的路径性能显著劣化。这正是解法二与解法三的本质差别。5.4 DFS 中 Trie 指针推进顺序错误先检查子节点是否存在再移动指针直接node node.children[char]再判空在哈希表版本会抛空指针/键不存在异常Go 版本返回 nil 解引用也会 panic先更新指针再检查isWord若在更新node之前就检查isWord会漏掉当前格子构成的单词。5.5 visited 集合与 Trie 配合不当使用独立 visited 集合时若每个新起点没有正确初始化或回溯清除visited 状态会阻塞合法路径。正确做法是每次 DFS 进入时visit.add、退出时visit.remove保证每条搜索路径拥有自己的访问历史。Go 版本用visit[r*COLSc]的一维键编码、Java 版本用r - c字符串键本质相同。6. 仓库源码索引9 种语言的实现对照本仓库在 README 完成度表格README.md中登记了该题的多语言实现以下是各语言文件的相对路径可与本文三种解法一一对照语言文件路径实现要点Pythonpython/0212-word-search-ii.pychildren字典 refsremoveWordDFS 中以refs 1剪枝Javajava/0212-word-search-ii.java内嵌Trie类refsremoveWordHashSet去重Ccpp/0212-word-search-ii.cppchildren[26]定长数组 isWord原地#标记找到后isWord falseGogo/0212-word-search-ii.gorefsremoveWordvisit[r*COLSc]一维访问标记JavaScriptjavascript/0212-word-search-ii.js面向对象封装Trie节点存完整word字符串找到后置空TypeScripttypescript/0212-word-search-ii.ts节点存word布尔标记.作为原地访问标记Cc/0212-word-search-ii.c手写TrieNodeparent指针用count计数、valid标记存活分支Kotlin / Swift / Rustkotlin/0212-word-search-ii.kt、swift/0212-word-search-ii.swift、rust/0212-word-search-ii.rs与解法三结构一致Rust 用OptionBoxTrieNode表达可断开的子节点其中 C 语言版本c/0212-word-search-ii.c值得特别关注它用parent指针在找到单词后自底向上遍历整条路径递减countcount 0的节点被置为valid false实现了与refs等价的引用计数剪枝——这印证了文档解法三引用计数 死分支标记思想在不同语言下的通用性。7. 总结LeetCode 212「Word Search II」是一道经典的网格 字典组合题其解题脉络清晰递进朴素回溯直观但低效逐词独立搜索适合作为热身理解Trie 哈希集合用前缀树共享搜索消灭重复前缀工作但缺少剪枝Trie refs 剪枝用引用计数把已找到的单词从 Trie 中物理移除死分支被切断是实战与面试中的最优解。掌握这道题的三个层次你就同时掌握了回溯的标记—递归—复原三板斧、Trie 的构建与遍历以及计数驱动的剪枝这一可迁移到其他字符串/网格组合题如 search-for-word.md、word-search-ii 同源变体的核心技巧。对照本仓库 9 种语言的实现逐一阅读还能顺带提升多语言视角下的数据结构建模能力。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/19 6:44:55 · 阅读 1.2k LeetCode 212 单词搜索 II 深度解析：从朴素回溯到 Trie 剪枝的三种解法（leetcode1/leetcode 项目实战）
LeetCode 212 单词搜索 II 深度解析从朴素回溯到 Trie 剪枝的三种解法leetcode1/leetcode 项目实战【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于 leetcode1/leetcode 仓库中的 search-for-word-ii.md 文档展开完整讲解 LeetCode 212「Word Search II」的三种递进式解法朴素回溯Backtracking、Trie 哈希集合、Trie 引用计数剪枝并结合仓库内 python/0212-word-search-ii.py、java/0212-word-search-ii.java、cpp/0212-word-search-ii.cpp 等 9 种语言源码印证实现细节。读完本文你将掌握二维网格 单词集合类问题的标准套路如何用 DFS 在网格中枚举路径、如何用 Trie 共享前缀搜索、以及如何用refs引用计数剪枝把性能推到极致。前置知识Prerequisites在动手解这道题之前需要先熟悉四个基础概念概念说明Backtracking回溯通过做出选择、递归探索、撤销选择来尝试所有可能的路径是穷举 复原的经典范式DFS深度优先搜索沿每条分支尽可能深入后再回溯用于遍历图或网格Trie前缀树一种树形数据结构用于高效的前缀匹配与单词存储让多个单词共享公共前缀2D Grid Traversal二维网格遍历在矩阵中沿上下左右四个方向移动同时处理越界边界这些概念在仓库中都有对应实现例如 implement-prefix-tree.md前缀树专题、search-for-word.md单词搜索版 Word Search I可作为递进阅读材料。而本仓库的 README.md 中 0212 一行的完成状态表显示该题在 C/C/C#/Go/Java/JavaScript/Kotlin/Python/Swift/TypeScript 等语言下均有通过实现。1. 解法一朴素回溯逐词搜索1.1 核心直觉对words中的每一个单词尝试在棋盘上描出它从匹配首字母的格子出发沿着上下左右相邻格子一步步走。为了不让同一个格子在一段单词路径中被重复使用临时把格子标记为已访问探索完成后再恢复——这正是经典回溯。如果某个单词的所有字符都能按顺序匹配上该单词就找到了加入结果集。1.2 算法步骤设ROWS、COLS为棋盘尺寸对words中每个word把每个格子(r, c)作为潜在起点仅当它匹配word[0]运行回溯函数backtrack(r, c, i)i 当前需要匹配的word下标基线条件i len(word)返回true整个单词已匹配若越界或棋盘格子不等于word[i]返回false将格子标记为已访问例如替换为*向 4 个邻居递归下标推进到i 1恢复原字符撤销选择返回是否存在某个邻居路径成功若任一起点成功把word加入答案并停止搜索该词。1.3 代码实现以下给出 Python / Java / C 三种代表实现仓库中 Go / Kotlin / Swift / Rust 版本可在本文末尾源码索引中找到class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: ROWS, COLS len(board), len(board[0]) res [] def backtrack(r, c, i): if i len(word): return True if (r 0 or c 0 or r ROWS or c COLS or board[r][c] ! word[i] ): return False board[r][c] * ret (backtrack(r 1, c, i 1) or backtrack(r - 1, c, i 1) or backtrack(r, c 1, i 1) or backtrack(r, c - 1, i 1)) board[r][c] word[i] return ret for word in words: flag False for r in range(ROWS): if flag: break for c in range(COLS): if board[r][c] ! word[0]: continue if backtrack(r, c, 0): res.append(word) flag True break return respublic class Solution { public ListString findWords(char[][] board, String[] words) { int ROWS board.length, COLS board[0].length; ListString res new ArrayList(); for (String word : words) { boolean flag false; for (int r 0; r ROWS !flag; r) { for (int c 0; c COLS; c) { if (board[r][c] ! word.charAt(0)) continue; if (backtrack(board, r, c, word, 0)) { res.add(word); flag true; break; } } } } return res; } private boolean backtrack(char[][] board, int r, int c, String word, int i) { if (i word.length()) return true; if (r 0 || c 0 || r board.length || c board[0].length || board[r][c] ! word.charAt(i)) return false; board[r][c] *; boolean ret backtrack(board, r 1, c, word, i 1) || backtrack(board, r - 1, c, word, i 1) || backtrack(board, r, c 1, word, i 1) || backtrack(board, r, c - 1, word, i 1); board[r][c] word.charAt(i); return ret; } }class Solution { public: vectorstring findWords(vectorvectorchar board, vectorstring words) { int ROWS board.size(), COLS board[0].size(); vectorstring res; for (string word : words) { bool flag false; for (int r 0; r ROWS !flag; r) { for (int c 0; c COLS; c) { if (board[r][c] ! word[0]) continue; if (backtrack(board, r, c, word, 0)) { res.push_back(word); flag true; break; } } } } return res; } private: bool backtrack(vectorvectorchar board, int r, int c, string word, int i) { if (i word.length()) return true; if (r 0 || c 0 || r board.size() || c board[0].size() || board[r][c] ! word[i]) return false; board[r][c] *; bool ret backtrack(board, r 1, c, word, i 1) || backtrack(board, r - 1, c, word, i 1) || backtrack(board, r, c 1, word, i 1) || backtrack(board, r, c - 1, word, i 1); board[r][c] word[i]; return ret; } };1.4 复杂度分析时间复杂度$O(w \times m \times n \times 4 \times 3^{t-1})$空间复杂度$O(t)$其中 $w$ 是单词个数$m$ 是行数$n$ 是列数$t$ 是words中最长单词的长度。为什么是 $4 \times 3^{t-1}$每次从当前格子出发第一步有 4 个方向可选进入路径后由于不能走回头路当前格子已被标记后续每一步最多只有 3 个有效方向。这种首步 4 选、其后 3 选的结构是网格回溯问题复杂度分析的核心。1.5 局限朴素回溯最大的浪费在于w个单词完全独立搜索彼此之间没有任何信息共享。若words [oath, oats, oak]三个单词共享前缀oa朴素回溯会为每个单词从零开始重新在棋盘上走一遍o - a的前缀路径重复劳动严重。这正是解法二引入 Trie 的动机。2. 解法二回溯 Trie 哈希集合2.1 核心直觉逐词搜索做了大量重复工作。Trie前缀树让这些工作得以共享在棋盘上行走时只继续那些匹配某个单词前缀的路径。于是棋盘 DFS 探索的是可能的前缀每当 Trie 节点表明此前缀是一个完整单词时就记录下来。同时为避免单条路径中重复使用同一格子需要在当前 DFS 路径中维护一个visited 集合返回时回溯/移除。2.2 算法步骤用所有words构建一棵 Trie每个 Trie 节点存储children下一层字母和isWord此处是否为某个单词的结尾初始化res为集合去重visit为当前 DFS 路径的访问集合定义dfs(r, c, node, wordSoFar)若(r, c)越界、已访问、或board[r][c]不在node.children中停止标记(r, c)为已访问移动 Trie 指针node node.children[board[r][c]]把当前字符追加到wordSoFar若node.isWord true把wordSoFar加入res用更新后的node和wordSoFar递归 4 个邻居上下左右回溯把(r, c)从visit中移除从每个格子(r, c)以 Trie 根节点为起点运行 DFS返回res中收集到的全部单词。2.3 代码实现Pythonclass TrieNode: def __init__(self): self.children {} self.isWord False def addWord(self, word): cur self for c in word: if c not in cur.children: cur.children[c] TrieNode() cur cur.children[c] cur.isWord True class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for w in words: root.addWord(w) ROWS, COLS len(board), len(board[0]) res, visit set(), set() def dfs(r, c, node, word): if (r 0 or c 0 or r ROWS or c COLS or (r, c) in visit or board[r][c] not in node.children ): return visit.add((r, c)) node node.children[board[r][c]] word board[r][c] if node.isWord: res.add(word) dfs(r 1, c, node, word) dfs(r - 1, c, node, word) dfs(r, c 1, node, word) dfs(r, c - 1, node, word) visit.remove((r, c)) for r in range(ROWS): for c in range(COLS): dfs(r, c, root, ) return list(res)Java 版本用boolean[][] visit二维数组代替哈希集合java/0212-word-search-ii.java 中为HashSetString存坐标字符串C 版本同样用vectorvectorboolGo 版本用map[[2]int]bool。三种做法在语义上完全等价只是去重/标记的数据结构不同。2.4 复杂度分析时间复杂度$O(m \times n \times 4 \times 3^{t-1} s)$空间复杂度$O(s)$其中 $m$ 是行数$n$ 是列数$t$ 是最长单词长度$s$ 是所有单词长度之和即 Trie 的规模。与解法一相比搜索部分的时间上界从w倍降为 1 倍所有单词共享同一趟前缀 DFS但额外付出 $O(s)$ 的空间构建 Trie。2.5 两个值得注意的细节去重结果集用setPythonset/ JavaHashSet/ Gomap[string]bool因为棋盘上可能存在多条路径拼出同一个单词直接 append 会产生重复项字符串传递word board[r][c]采用不可变字符串逐层传递Python/JavaGo 版本同样用word string(char)而 Rust 版本rust/0212-word-search-ii.rs用word.push(ch) 回溯word.pop()复用同一可变缓冲区避免每层拷贝。3. 解法三回溯 Trie引用计数剪枝推荐3.1 核心直觉解法二仍会在已无剩余单词的分支上继续探索。解法三在 Trie 上引入激进剪枝每个 Trie 节点维护refs 字典中还有多少个单词经过该节点成功找到一个或多个单词后每个 DFS 调用向上返回它在当前前缀下新找到的单词数量随着 DFS 回溯从该路径上的每个 Trie 节点减去这个数量把已找到的单词从所有相关节点移除若某节点refs减到0说明该分支已死亡没有剩余单词用到它直接把父节点的指针切断prev.children[...] null让后续 DFS 永远不会再探索这些无用的前缀。此外不再使用独立的 visited 集合而是原地标记棋盘探索某条路径时临时把board[r][c]设为*回溯时恢复原字符。3.2 Trie 节点存储什么每个节点包含字段含义children[26]下一层字母定长数组比哈希表更快idx若此处是某单词结尾记录其在words中的下标否则为-1refs仍存活的、经过该节点的单词数量含在此结束的单词3.3 算法步骤构建 Trie插入每个words[i]插入过程中路径上的每个节点refs加 1结尾节点记录idx i从每个棋盘格子运行dfs(r, c, node)尝试用board[r][c]扩展当前 Trie 路径DFS 规则若越界、当前格子已是*路径内已用、或 Trie 中没有board[r][c]对应的子节点停止否则取字母ch board[r][c]移动到子节点child node.children[ch]标记格子board[r][c] *若child.idx ! -1找到单词把words[child.idx]加入结果置child.idx -1防重复初始化found 1向 4 个邻居以child递归累加返回数量到found令child.refs - found若child.refs 0切断该分支node.children[ch] null恢复棋盘格子返回found使每个祖先节点都能更新自己的refs每次顶层 DFS 结束后root.refs减去返回值返回收集到的结果。3.4 代码实现Pythonclass TrieNode: def __init__(self): self.children [None] * 26 self.idx -1 self.refs 0 def addWord(self, word, i): cur self cur.refs 1 for c in word: index ord(c) - ord(a) if not cur.children[index]: cur.children[index] TrieNode() cur cur.children[index] cur.refs 1 cur.idx i class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for i in range(len(words)): root.addWord(words[i], i) ROWS, COLS len(board), len(board[0]) res [] def getIndex(c): index ord(c) - ord(a) return index def dfs(r, c, node): if (r 0 or c 0 or r ROWS or c COLS or board[r][c] * or not node.children[getIndex(board[r][c])]): return 0 tmp board[r][c] board[r][c] * prev node node node.children[getIndex(tmp)] found 0 if node.idx ! -1: res.append(words[node.idx]) node.idx -1 found 1 found dfs(r 1, c, node) found dfs(r - 1, c, node) found dfs(r, c 1, c, node) if False else dfs(r, c 1, node) found dfs(r, c - 1, node) board[r][c] tmp node.refs - found if not node.refs: prev.children[getIndex(tmp)] None return found for r in range(ROWS): for c in range(COLS): root.refs - dfs(r, c, root) return res上例中dfs(r, c 1, node)的写法请以文档原文为准原文为dfs(r, c 1, node)。注意原始文档该解法为children定长数组26Java/C/C#/Go/Kotlin/Swift/Rust 版本均遵循c - a映射到数组下标的结构例如 cpp/0212-word-search-ii.cpp 中的children[26]与node-children[board[r][c] - a]。3.5 复杂度分析时间复杂度$O(m \times n \times 4 \times 3^{t-1} s)$空间复杂度$O(s)$其中 $m$ 是行数$n$ 是列数$t$ 是最长单词长度$s$ 是所有单词长度之和。虽然理论上界与解法二相同但refs剪枝让实际运行时间显著更优一旦某分支剩余单词数为 0物理切断指针后后续所有从其他起点发起的 DFS 都直接跳过该分支避免了对死前缀的重复探索。4. 三种解法对比总览维度解法一朴素回溯解法二Trie 哈希集合解法三Trie refs 剪枝是否共享前缀否逐词独立是是访问标记原地*独立 visited 集合原地*去重方式逐词只加一次结果集合setidx -1剪枝策略无无仅前缀匹配refs计数 断链时间上界$O(w \cdot m \cdot n \cdot 4 \cdot 3^{t-1})$$O(m \cdot n \cdot 4 \cdot 3^{t-1} s)$$O(m \cdot n \cdot 4 \cdot 3^{t-1} s)$空间上界$O(t)$$O(s)$$O(s)$实战性能最差重复前缀搜索中等最优死分支被物理剪除解法三既是面试中的加分答案也是仓库中各语言实现的主流形态。5. 常见陷阱与规避Common Pitfalls5.1 忘记对结果去重棋盘上多条路径可能拼出同一个单词直接加入结果列表会产生重复项。规避方式有两种结果用集合set存储在 Trie 中标记单词已被找到把结尾节点的idx置为-1解法三或把isWord/word置空解法二变体。例如仓库 javascript/0212-word-search-ii.js 中checkWord找到单词后执行node.word 正是标记已找到的写法python/0212-word-search-ii.py 则同时用node.isWord False与res集合双重保险。5.2 回溯后没有恢复棋盘直接在棋盘上标记如board[r][c] *后若递归结束忘记恢复原字符棋盘状态被破坏其他起点或其他单词将无法找到有效路径。正确做法是保存tmp board[r][c]在递归返回后恢复。5.3 构建了 Trie 却不剪枝建好 Trie 但找到单词后不剪枝会导致持续探索死分支没有递减refs、没有在refs归零时删除节点算法就会继续搜索不可能产生新单词的路径性能显著劣化。这正是解法二与解法三的本质差别。5.4 DFS 中 Trie 指针推进顺序错误先检查子节点是否存在再移动指针直接node node.children[char]再判空在哈希表版本会抛空指针/键不存在异常Go 版本返回 nil 解引用也会 panic先更新指针再检查isWord若在更新node之前就检查isWord会漏掉当前格子构成的单词。5.5 visited 集合与 Trie 配合不当使用独立 visited 集合时若每个新起点没有正确初始化或回溯清除visited 状态会阻塞合法路径。正确做法是每次 DFS 进入时visit.add、退出时visit.remove保证每条搜索路径拥有自己的访问历史。Go 版本用visit[r*COLSc]的一维键编码、Java 版本用r - c字符串键本质相同。6. 仓库源码索引9 种语言的实现对照本仓库在 README 完成度表格README.md中登记了该题的多语言实现以下是各语言文件的相对路径可与本文三种解法一一对照语言文件路径实现要点Pythonpython/0212-word-search-ii.pychildren字典 refsremoveWordDFS 中以refs 1剪枝Javajava/0212-word-search-ii.java内嵌Trie类refsremoveWordHashSet去重Ccpp/0212-word-search-ii.cppchildren[26]定长数组 isWord原地#标记找到后isWord falseGogo/0212-word-search-ii.gorefsremoveWordvisit[r*COLSc]一维访问标记JavaScriptjavascript/0212-word-search-ii.js面向对象封装Trie节点存完整word字符串找到后置空TypeScripttypescript/0212-word-search-ii.ts节点存word布尔标记.作为原地访问标记Cc/0212-word-search-ii.c手写TrieNodeparent指针用count计数、valid标记存活分支Kotlin / Swift / Rustkotlin/0212-word-search-ii.kt、swift/0212-word-search-ii.swift、rust/0212-word-search-ii.rs与解法三结构一致Rust 用OptionBoxTrieNode表达可断开的子节点其中 C 语言版本c/0212-word-search-ii.c值得特别关注它用parent指针在找到单词后自底向上遍历整条路径递减countcount 0的节点被置为valid false实现了与refs等价的引用计数剪枝——这印证了文档解法三引用计数 死分支标记思想在不同语言下的通用性。7. 总结LeetCode 212「Word Search II」是一道经典的网格 字典组合题其解题脉络清晰递进朴素回溯直观但低效逐词独立搜索适合作为热身理解Trie 哈希集合用前缀树共享搜索消灭重复前缀工作但缺少剪枝Trie refs 剪枝用引用计数把已找到的单词从 Trie 中物理移除死分支被切断是实战与面试中的最优解。掌握这道题的三个层次你就同时掌握了回溯的标记—递归—复原三板斧、Trie 的构建与遍历以及计数驱动的剪枝这一可迁移到其他字符串/网格组合题如 search-for-word.md、word-search-ii 同源变体的核心技巧。对照本仓库 9 种语言的实现逐一阅读还能顺带提升多语言视角下的数据结构建模能力。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考