单词搜索 II：Trie + 网格回溯
将所有目标单词插入 Trie，并在二维棋盘上运行 DFS 回溯，同时查找所有有效单词，时间复杂度为 O(m × n × 4^L)。
单词搜索 II：Trie + 网格回溯 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
单词搜索 II 问题
单词搜索 II（LeetCode 212）：给定一个由字符组成的 m × n 棋盘和一个单词列表，找出所有能够由连续相邻单元格组成的单词（只能水平或垂直相邻），且每个单元格只能使用一次。这比单词搜索 I（查找单个单词）更难，因为我们需要同时 find 所有匹配的单词——如果直接为每个单词运行一次单词搜索 I，复杂度为 O(W × m × n × 4^L)，速度会太慢。
为什么使用字典树和回溯
将所有目标单词插入字典树，然后在棋盘上运行 DFS 回溯，就可以同时 search 所有单词。在每个棋盘单元格处，我们不再检查“这条路径是否拼出了目标单词”，而是检查“这条路径是否匹配字典树中的某个前缀”。一旦字典树前缀匹配失败，就立即剪掉整个 DFS 分支，从而避免对共享此前缀的所有单词重复执行工作。
从单词列表构建字典树
将所有单词插入字典树。在叶节点的 node.word 中存储完整单词，而不只是存储一个布尔值。这样，在回溯过程中找到完整匹配时，就可以立即将该单词加入结果，而无需逐个字符重新构造。
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')在网格上进行 DFS 回溯
从棋盘上的每个单元格启动一次 DFS。每一步执行以下操作：(1) 检查当前单元格的字符是否是当前字典树节点的子节点；(2) 如果是，则将该单元格标记为已访问（将其设置为类似 '#' 的哨兵值），再递归处理四个相邻单元格；(3) 递归结束后恢复该单元格（取消标记）。当字典树节点的 word 不为空时，将其加入结果，并将其设置为空值，以避免 duplicates。
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']复杂度分析
时间复杂度：O(m × n × 4^L)，其中 L 是最长单词的长度。对于 m×n 个起始单元格中的每一个，DFS 最多会探索 4^L 条路径。字典树会剪掉与任何单词前缀都不匹配的路径，因此实际速度会快得多。构建字典树的复杂度为 O(W × L)，其中 W 是单词数量。空间复杂度：字典树需要 O(W × L)，递归栈深度需要 O(L)。
剪枝：找到单词后移除叶节点
找到一个单词后，如果叶节点没有子节点，应当从字典树中移除该叶节点，而不只是将单词置空。这样可以避免后续 DFS 调用再次访问无效分支。当找到单词后某个节点的子节点变为空时，就从其父节点的子节点字典中移除该节点。当许多单词共享很长的前缀时，这项优化非常重要。
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')为什么在节点中存储单词更好
在字典树叶节点中存储完整单词（而不是从 DFS 路径重新构造）有两个优点：(1) 找到匹配项时可以用 O(1) 时间获取单词，而不必用 O(L) 时间重建路径；(2) 找到单词后将 node.word = None 设为空值，就能以 O(1) 的方式简洁去重，无需额外的结果集合。对于单词搜索 II，防止重复尤其重要，因为理论上同一个单词可能通过不同路径找到。
原地标记已访问单元格
我们不使用单独的 visited 集合（否则每条 DFS 路径都需要 O(m × n) 的空间），而是通过将单元格中的字符替换为类似 '#' 的哨兵值来进行原地标记。DFS 返回后，再恢复原字符。这种技术：(1) 每个单元格只使用 O(1) 的额外空间；(2) 自动防止在同一条路径中重复访问；(3) 对字典树遍历完全透明，因为 '#' 永远不会出现在字典树中。
需要处理的边界情况
重要的边界情况包括：(1) 单词列表中存在重复单词——可以使用集合，或利用 node.word = None 的技巧防止结果重复；(2) 单词过长，超出棋盘尺寸——这些单词无法组成，但 DFS 会因没有相邻单元格可继续而自然结束；(3) 只有一个单元格的棋盘——只能找到单字符单词；(4) 同一个单词可以通过不同路径找到——node.word = None 的技巧可以防止重复计数。
与朴素方法的比较
朴素方法是：对于 W 个单词中的每一个，都运行一次单词搜索 I，复杂度为 O(W × m × n × 4^L)。使用字典树后，可以同时 search 所有单词，复杂度为 O(m × n × 4^L)，与 W 无关。当棋盘为 10×10、单词数量 W=1000 且每个单词长度为 10 时，朴素方法比字典树慢 1000 倍。字典树充当共享的前缀过滤器，将成本分摊到所有单词上，这是利用数据结构实现渐进改进的经典示例。
完整解决方案总结
单词搜索 II 的完整解决方案：使用单词构建字典树，并在叶节点存储单词字符串。对于棋盘中的每个单元格，运行 DFS：检查当前字符是否存在于当前字典树节点中，将单元格标记为 '#'，递归处理四个相邻单元格，然后恢复该单元格。当节点中的单词字段非空时，将其加入结果并置空。使用后也可以剪掉空的字典树分支。最后返回结果列表。时间复杂度：O(m×n×4^L)；空间复杂度：O(W×L) 的字典树加 O(L) 的递归空间。
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result快速检查
检验您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课您学习了：单词搜索 II 使用字典树，通过共享前缀剪枝实现多单词同时搜索；将单词字符串存储在字典树叶节点中，可以用 O(1) 时间获取单词，并在找到后将其设为空值，从而轻松去重；以及使用 '#' 原地标记已访问单元格，避免每条 DFS 路径产生 O(m×n) 的额外空间。至此，字典树与字符串算法课程就完成了——您已经掌握了面试中最强大的字符串专用数据结构之一。
常见问题解答
「单词搜索 II：Trie + 网格回溯」课时是免费的吗？
是的 — 「单词搜索 II：Trie + 网格回溯」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「单词搜索 II：Trie + 网格回溯」这节课中我会学到什么？
将所有目标单词插入 Trie，并在二维棋盘上运行 DFS 回溯，同时查找所有有效单词，时间复杂度为 O(m × n × 4^L)。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「单词搜索 II：Trie + 网格回溯」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- TrieNode 类：插入与搜索
- 前缀搜索与 Starts-With
- Trie 中的通配符与正则搜索
- 单词搜索 II：Trie + 网格回溯