LeetCode 212. 单词搜索 II

题目描述
给定一个 m x n 二维字符网格 board 和一个单词列表 words，你需要返回所有同时在网格中出现的单词。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例

board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

输出：["eat","oath"]

解题思路
如果对 words 中的每个单词单独执行回溯搜索（类似 LeetCode 79. 单词搜索），在单词数量多、网格大的情况下会超时，因为会有大量重复搜索。
高效的解法是使用 Trie（前缀树） 来预处理单词列表，然后在网格上以每个单元格为起点，沿 Trie 的路径进行 DFS 回溯搜索。一旦找到一个单词，就将其加入结果，并且在 Trie 中标记该单词已找到，避免重复记录。

步骤详解

1. 定义 Trie 节点结构
每个节点包含：

• 子节点字典（字符 → 子节点）
• 是否是单词结尾
• 单词本身（在结尾时存储，方便直接加入结果）

2. 构建 Trie
遍历 words 列表，将每个单词插入 Trie 中。

3. 回溯搜索
遍历网格的每个单元格 (i, j)，如果当前字符在 Trie 根节点的子节点中，则从该单元格开始进行 DFS 回溯：

• 检查当前位置是否越界、单元格是否访问过、当前字符是否在当前 Trie 节点的子节点中，不满足则返回。
• 移动到 Trie 中对应字符的子节点。
• 如果该子节点对应一个单词，将单词加入结果集，并且将该节点的单词标记清空，避免重复添加。
• 如果该子节点还有子节点（即还可能构成更长的单词），则继续向四个方向 DFS。
• 回溯时恢复单元格的访问状态。

4. 优化
在回溯中，如果当前 Trie 节点已经没有子节点，可以在 Trie 中删除该节点（剪枝），减少后续搜索。这里为了简化可以先不实现删除，但要知道这个优化点。

详细过程举例
以上面的示例为例：

1. 构建 Trie：

   • 插入 "oath"：根 → o → a → t → h，h 节点存单词 "oath"
   • 插入 "pea"：p → e → a，a 节点存单词 "pea"
   • 插入 "eat"：e → a → t，t 节点存单词 "eat"
   • 插入 "rain"：r → a → i → n，n 节点存单词 "rain"

2. 从 board[0][0]='o' 开始：

   • Trie 根有子节点 'o'，进入。
   • 从 (0,0) 向四个方向 DFS，下边 (1,0)='e'，但 Trie 中 'o' 的子节点没有 'e'，此路不通。右 (0,1)='a'，'o' 的子节点是 'a'，继续。
   • 路径 "oa" 之后，接着找 't'，找到，再找 'h'，找到，此时在 Trie 中到达节点 h，发现它存了单词 "oath"，加入结果。
   • 继续搜索，但 h 没有子节点，回溯。

3. 从 board[1][0]='e' 开始：

   • Trie 根有子节点 'e'，进入。
   • 向右 (1,1)='t'，但 e → a 才有 t，这里 e 的直接子节点是 'a' 吗？没有，所以不通。向下 (2,0)='i' 也不在 e 的子节点中。但注意 e 本身也是一个单词吗？不是，words 里是 "eat"，不是 "e"。
   • 实际正确搜索：
     • (1,0)='e' → 下 (2,0)='i' 不行，右 (1,1)='t' 不行，左不行，上不行。其实 e 必须接 a 才能继续。看 (2,0)='i' 不是 a，所以从 (1,0) 开始无法形成 "eat"。
     • 真正找到 "eat" 是从 (1,2)='a' 吗？不对，看 board：
       eat 路径：从 (2,0)='i' 开始不行，看 (1,1)='t' 不行。我们换一个起点：(0,3)='n' 不是 e。
     • 注意 "eat" 存在于 board 中：路径是 (1,0)='e' → (1,1)='t' 不对，应该是 (1,0)='e' → (0,1)='a' → (1,1)='t' 吗？检查坐标连续性：
       (1,0) e → (0,1) a 是相邻（对角线不算，所以不行，必须上下左右）。所以不行。
       实际上 "eat" 路径是 (1,3)='e' → (2,3)='r'? 不对，看 board：
       (1,3)='e', (2,3)='r' 不是 a。我们重新搜索：
     • 正确路径：从 (0,1)='a' 开始不行，因为 e 开头。看 (1,3)='e' 相邻有 (0,3)='n' 和 (2,3)='r' 和 (1,2)='a'。e→a 可行，然后 a→t，t 在 (0,2)='a'? 不是 t，在 (2,2)='l'? 不是，在 (1,1)='t' 是的，所以路径是：
       (1,3) e → (1,2) a → (1,1) t，这就是 "eat"。

4. 回溯过程中标记已访问单元格，避免重复使用。

最终代码框架（Python风格，无具体实现细节，只展示结构）

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # 存储到该节点结束的单词

class Solution:
    def findWords(self, board, words):
        # 1. 构建 Trie
        root = TrieNode()
        for w in words:
            node = root
            for ch in w:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.word = w
        
        # 2. 回溯搜索
        m, n = len(board), len(board[0])
        res = []
        
        def dfs(i, j, node):
            ch = board[i][j]
            if ch not in node.children:
                return
            nxt = node.children[ch]
            if nxt.word:
                res.append(nxt.word)
                nxt.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, nxt)
            # 回溯
            board[i][j] = ch
            
            # 可选的剪枝：如果 nxt 没有子节点，删除它
            if not nxt.children:
                node.children.pop(ch)
        
        for i in range(m):
            for j in range(n):
                dfs(i, j, root)
        
        return res

总结
这个问题的核心是 Trie + 回溯搜索。

• Trie 用于快速匹配前缀，避免对网格重复搜索。
• 回溯时注意恢复状态。
• 去重技巧：找到单词后将 Trie 节点的 word 清空。
  时间复杂度：最坏情况 O(m×n×4^L)，L 是单词最大长度，但 Trie 剪枝后实际运行很快。