哈希算法题目：单词搜索 II

字数 2597 2025-10-29 11:31:55

哈希算法题目：单词搜索 II

题目描述
给定一个 m x n 的二维网格 board 和一个单词列表 words。你需要找出所有在网格中出现的单词，并返回这些单词的列表。单词必须按照字母顺序，通过相邻的单元格（相邻指上下左右相邻）的字母构成。同一个单元格内的字母在一个单词中不允许被重复使用。

解题过程

步骤1：理解问题与约束

输入：一个字符网格 board 和一个单词列表 words。
输出：所有能在网格中按规则找到的单词列表。
规则：
1. 单词由相邻（上下左右）单元格的字母连续构成。
2. 在构成一个单词时，同一个单元格的字母只能使用一次。
3. 返回的单词列表需要去重并按字典序排序。

步骤2：分析暴力解法的不足
最直观的方法是，对于 words 中的每个单词，在网格 board 中使用深度优先搜索（DFS）去查找是否存在。假设 words 中有 W 个单词，网格大小为 M x N，平均单词长度为 L。

时间复杂度：最坏情况下，对每个单词，我们需要在网格的每个起点（MN 个）进行 DFS（每个方向最多 4^L 次探索）。总复杂度约为 O(W M * N * 4^L)。当单词列表很大时，这会非常慢。

步骤3：引入哈希算法与前缀树（Trie）
为了优化，我们需要避免对网格进行大量重复的DFS搜索。核心思想是：同时查找所有单词，而不是一个一个地查找。

前缀树（Trie）：这是一种树形数据结构，用于高效地存储和检索字符串集合。它的键不是直接保存在节点中，而是由节点在树中的位置决定。从根节点到某个节点的路径代表一个字符串（或前缀）。
哈希思想的应用：虽然前缀树本身不是传统的哈希表，但它体现了哈希的思想——通过字符（作为键）快速定位到下一个节点（作为值），实现快速的前缀匹配。

步骤4：构建解题框架

构建前缀树：将 words 中的所有单词插入到一棵前缀树中。
DFS遍历网格：对网格 board 中的每一个单元格 (i, j) 作为起点，开始进行DFS搜索。
在前缀树中匹配：在DFS过程中，将当前路径形成的字符串与前缀树进行匹配。如果当前路径不是任何单词的前缀，则立即剪枝（回溯），不再继续搜索。如果当前路径正好是前缀树中某个单词的结尾，则将该单词加入结果集。
避免重复使用单元格：在DFS过程中，使用一个访问标记数组，或者通过临时修改 board[i][j] 为一个特殊字符（如 ‘#’）来标记该单元格已被当前路径使用。在回溯时，需要恢复该单元格的原始值。

步骤5：详细步骤分解

5.1 定义前缀树节点（TrieNode）
每个节点包含：

children: Dict[str, TrieNode]：一个字典（哈希表），键是字符，值是对应的子节点。这实现了字符到节点的快速映射。
word: Optional[str]：如果该节点是某个单词的结尾，则存储这个完整的单词；否则为 None。这样在找到单词时可以直接记录，无需重新拼接字符串。

5.2 构建前缀树（Trie）

创建一个根节点（root）。
遍历 words 列表中的每个单词。
对于每个单词，从根节点开始，逐个插入字符：
- 如果当前字符不在当前节点的 children 字典中，就创建一个新的 TrieNode 并加入。
- 移动到对应字符的子节点。
在插入完单词的最后一个字符后，在该节点上记录这个完整的单词（node.word = word）。

5.3 深度优先搜索（DFS）函数
定义一个递归函数 dfs(node, i, j)：

node：当前在前缀树中匹配到的节点。
i, j：当前在网格中探索的坐标。

函数执行步骤：

检查当前节点：检查 node.word 是否存在。如果存在，说明我们找到了一个单词。将其加入结果集，然后将 node.word 置为 None（防止同一单词被重复添加，例如网格中有多条路径能形成同一个单词）。
检查边界与访问状态：检查坐标 (i, j) 是否在网格范围内，以及该单元格是否已被访问过（例如 board[i][j] == '#'）。
检查字符匹配：获取当前网格的字符 ch = board[i][j]。检查这个字符 ch 是否在当前 Trie 节点 node 的 children 字典中。如果不在，说明当前路径不构成任何单词的前缀，直接返回（剪枝）。
标记访问：将 board[i][j] 临时标记为 ‘#’，表示已访问。
递归探索四个方向：获取匹配到的子节点 next_node = node.children[ch]。然后分别向上、下、左、右四个方向进行DFS：dfs(next_node, i+dx, j+dy)。
回溯恢复状态：在递归调用返回后，将 board[i][j] 恢复为原来的字符 ch，撤销访问标记。

5.4 主函数流程

初始化一个空列表 result 用于存储找到的单词。
根据 words 构建前缀树 trie。
遍历网格 board 的每一个单元格 (i, j)：
- 以根节点和当前坐标 (i, j) 为参数，调用 dfs(trie.root, i, j)。
DFS 过程会不断将找到的单词添加到 result 中。
由于题目要求返回的列表按字典序排序，且我们在插入单词时可能顺序是乱的，最后需要对 result 进行排序并返回。但通常我们找到单词的顺序并不影响，因为最终会排序。也可以使用集合来去重，最后再排序。

步骤6：复杂度分析

时间复杂度：最坏情况需要遍历网格中的每个单元格（MN），DFS的深度最多为最长单词的长度 L。但由于前缀树的剪枝，实际探索的路径数远小于 4^L。整体复杂度优于 O(M N * 4^L)。
空间复杂度：主要来自前缀树的空间 O(Σ单词长度)，以及DFS递归栈的空间 O(L)。

总结
这道题的关键在于将哈希思想（通过字符快速映射）与前缀树数据结构结合，将“在网格中查找多个单词”的问题，转化为“用网格中的路径去匹配前缀树”，从而利用前缀树实现高效剪枝，避免了大量无效的搜索。DFS负责探索网格中的路径，而前缀树则像一个智能的“单词指南”，实时告诉我们当前路径是否值得继续走下去。

哈希算法题目：单词搜索 II 题目描述给定一个 m x n 的二维网格 board 和一个单词列表 words。你需要找出所有在网格中出现的单词，并返回这些单词的列表。单词必须按照字母顺序，通过相邻的单元格（相邻指上下左右相邻）的字母构成。同一个单元格内的字母在一个单词中不允许被重复使用。解题过程步骤1：理解问题与约束输入：一个字符网格 board 和一个单词列表 words。输出：所有能在网格中按规则找到的单词列表。规则：单词由相邻（上下左右）单元格的字母连续构成。在构成一个单词时，同一个单元格的字母只能使用一次。返回的单词列表需要去重并按字典序排序。步骤2：分析暴力解法的不足最直观的方法是，对于 words 中的每个单词，在网格 board 中使用深度优先搜索（DFS）去查找是否存在。假设 words 中有 W 个单词，网格大小为 M x N，平均单词长度为 L。时间复杂度：最坏情况下，对每个单词，我们需要在网格的每个起点（M N 个）进行 DFS（每个方向最多 4^L 次探索）。总复杂度约为 O(W M * N * 4^L)。当单词列表很大时，这会非常慢。步骤3：引入哈希算法与前缀树（Trie）为了优化，我们需要避免对网格进行大量重复的DFS搜索。核心思想是：同时查找所有单词，而不是一个一个地查找。前缀树（Trie）：这是一种树形数据结构，用于高效地存储和检索字符串集合。它的键不是直接保存在节点中，而是由节点在树中的位置决定。从根节点到某个节点的路径代表一个字符串（或前缀）。哈希思想的应用：虽然前缀树本身不是传统的哈希表，但它体现了哈希的思想——通过字符（作为键）快速定位到下一个节点（作为值），实现快速的前缀匹配。步骤4：构建解题框架构建前缀树：将 words 中的所有单词插入到一棵前缀树中。 DFS遍历网格：对网格 board 中的每一个单元格 (i, j) 作为起点，开始进行DFS搜索。在前缀树中匹配：在DFS过程中，将当前路径形成的字符串与前缀树进行匹配。如果当前路径不是任何单词的前缀，则立即剪枝（回溯），不再继续搜索。如果当前路径正好是前缀树中某个单词的结尾，则将该单词加入结果集。避免重复使用单元格：在DFS过程中，使用一个访问标记数组，或者通过临时修改 board[ i][ j ] 为一个特殊字符（如 ‘#’）来标记该单元格已被当前路径使用。在回溯时，需要恢复该单元格的原始值。步骤5：详细步骤分解 5.1 定义前缀树节点（TrieNode）每个节点包含： children: Dict[str, TrieNode] ：一个字典（哈希表），键是字符，值是对应的子节点。这实现了字符到节点的快速映射。 word: Optional[str] ：如果该节点是某个单词的结尾，则存储这个完整的单词；否则为 None。这样在找到单词时可以直接记录，无需重新拼接字符串。 5.2 构建前缀树（Trie）创建一个根节点（root）。遍历 words 列表中的每个单词。对于每个单词，从根节点开始，逐个插入字符：如果当前字符不在当前节点的 children 字典中，就创建一个新的 TrieNode 并加入。移动到对应字符的子节点。在插入完单词的最后一个字符后，在该节点上记录这个完整的单词（ node.word = word ）。 5.3 深度优先搜索（DFS）函数定义一个递归函数 dfs(node, i, j) ： node ：当前在前缀树中匹配到的节点。 i, j ：当前在网格中探索的坐标。函数执行步骤：检查当前节点：检查 node.word 是否存在。如果存在，说明我们找到了一个单词。将其加入结果集，然后将 node.word 置为 None（防止同一单词被重复添加，例如网格中有多条路径能形成同一个单词）。检查边界与访问状态：检查坐标 (i, j) 是否在网格范围内，以及该单元格是否已被访问过（例如 board[i][j] == '#' ）。检查字符匹配：获取当前网格的字符 ch = board[i][j] 。检查这个字符 ch 是否在当前 Trie 节点 node 的 children 字典中。如果不在，说明当前路径不构成任何单词的前缀，直接返回（剪枝）。标记访问：将 board[i][j] 临时标记为 ‘#’，表示已访问。递归探索四个方向：获取匹配到的子节点 next_node = node.children[ch] 。然后分别向上、下、左、右四个方向进行DFS： dfs(next_node, i+dx, j+dy) 。回溯恢复状态：在递归调用返回后，将 board[i][j] 恢复为原来的字符 ch ，撤销访问标记。 5.4 主函数流程初始化一个空列表 result 用于存储找到的单词。根据 words 构建前缀树 trie 。遍历网格 board 的每一个单元格 (i, j)：以根节点和当前坐标 (i, j) 为参数，调用 dfs(trie.root, i, j) 。 DFS 过程会不断将找到的单词添加到 result 中。由于题目要求返回的列表按字典序排序，且我们在插入单词时可能顺序是乱的，最后需要对 result 进行排序并返回。但通常我们找到单词的顺序并不影响，因为最终会排序。也可以使用集合来去重，最后再排序。步骤6：复杂度分析时间复杂度：最坏情况需要遍历网格中的每个单元格（M N），DFS的深度最多为最长单词的长度 L。但由于前缀树的剪枝，实际探索的路径数远小于 4^L。整体复杂度优于 O(M N * 4^L)。空间复杂度：主要来自前缀树的空间 O(Σ单词长度)，以及DFS递归栈的空间 O(L)。总结这道题的关键在于将哈希思想（通过字符快速映射）与前缀树数据结构结合，将“在网格中查找多个单词”的问题，转化为“用网格中的路径去匹配前缀树”，从而利用前缀树实现高效剪枝，避免了大量无效的搜索。DFS负责探索网格中的路径，而前缀树则像一个智能的“单词指南”，实时告诉我们当前路径是否值得继续走下去。