哈希算法题目：实现一个魔法字典

题目描述

设计一个魔法字典，它包含一个单词列表。实现两个主要方法：

1. buildDict(dictionary)：使用字符串列表 dictionary 初始化这个数据结构。
2. search(searchWord)：给定一个字符串 searchWord，判断能否只恰好替换一个字母，使得替换后得到的新单词存在于你之前构建的字典中。如果可以，返回 true；否则，返回 false。

注意：

• 你可以假设所有输入的单词都由小写字母 a-z 组成。
• 在 search 操作中，替换必须恰好是一个字母，不能是增加或删除。
• 替换后得到的新单词必须存在于初始化时使用的字典中。

示例：

MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 false，因为必须恰好替换一个字母，这里完全匹配不行
magicDictionary.search("hhllo"); // 返回 true，将 'h' 替换为 'e' 得到 "hello"
magicDictionary.search("hell"); // 返回 false，替换一个字母无法变成列表中的单词
magicDictionary.search("leetcoded"); // 返回 false

解题思路

这道题的核心在于高效地判断：在字典中，是否存在一个单词，它与待搜索的单词长度相同，且恰好只有一个位置的字符不同。

一种直接的思路是：对于每个 searchWord，遍历整个字典，与字典中每个单词逐个字符比较。但这样效率较低，特别是字典很大时。

更优化的方法是利用哈希表进行预处理：

• 关键观察：如果两个单词长度相同且恰好只有一个字符不同，那么我们可以为每个单词生成一系列“通配符”模式。例如，对于单词 "hello"，我们可以依次将每个位置替换为一个特殊字符（如 '*'），得到模式："*ello", "h*llo", "he*lo", "hel*o", "hell*"。
• 如果一个单词与 searchWord 满足条件，那么它们必然在某一个位置上，拥有相同的“通配符”模式。
• 因此，我们可以提前为字典中的每个单词生成其所有的通配符模式，并用哈希表记录下来。在搜索时，我们也为 searchWord 生成所有通配符模式，并检查哈希表中是否存在相同的模式。

但有一个细节需要注意：如果字典中存在与 searchWord 完全相同的单词，我们不能直接认为搜索成功，因为题目要求必须恰好替换一个字母。例如，字典中有 "hello"，搜索 "hello" 应该返回 false。因此，我们需要在哈希表中记录每个模式对应哪些原始单词，以便在匹配模式时，排除掉与 searchWord 完全相同的单词。

解题步骤

步骤1：数据结构设计

我们将使用一个哈希表（在Python中用字典，在Java中用HashMap等），键是“通配符模式”，值是一个列表，存储所有能生成该模式的原始单词。

例如，对于单词 "hello"，我们会生成以下键值对：

• 键 "*ello"，值列表包含 "hello"
• 键 "h*llo"，值列表包含 "hello"
• ...
  对于字典 ["hello", "hallo"]，单词 "hallo" 也会生成模式 "h*llo"。此时，键 "h*llo" 对应的值列表就会包含 "hello" 和 "hallo" 两个单词。

步骤2：实现 buildDict 方法

1. 初始化一个空的哈希表 self.pattern_map。
2. 遍历输入字典中的每个单词 word。
3. 对于 word 的每个位置 i（从0到 len(word)-1），生成一个模式字符串：
   • 将 word 在位置 i 的字符替换为一个通配符（例如 '*'）。
   • 注意：在Python中，字符串不可变，我们可以通过切片和拼接来生成：word[:i] + '*' + word[i+1:]。
4. 将这个模式作为键，将原始单词 word 添加到该键对应的值列表中。如果键不存在，先创建一个新列表。

步骤3：实现 search 方法

1. 对于输入的 searchWord，同样生成其所有的通配符模式（方法与 buildDict 中相同）。
2. 遍历每个生成的模式 pattern：
   • 检查 pattern 是否存在于哈希表 self.pattern_map 中。
   • 如果存在，获取该模式对应的原始单词列表 word_list。
   • 遍历 word_list 中的每个单词 candidate：
     • 如果 candidate 的长度与 searchWord 相同，但 candidate 不等于 searchWord 本身，那么就说明我们找到了一个字典中的单词，它可以通过替换 searchWord 中的一个字符得到（因为它们在同一个模式上匹配，意味着只有一个位置的字符不同）。此时，返回 true。
3. 如果遍历完所有模式，都没有找到满足条件的单词，则返回 false。

复杂度分析

• 构建时间复杂度：O(N * L)，其中 N 是字典中的单词数量，L 是单词的平均长度。我们需要为每个单词的每个位置生成模式。
• 搜索时间复杂度：O(L^2) 或 O(L + N')。生成所有模式需要 O(L)，但为了严谨，我们考虑在最坏情况下，每个模式都对应一个很长的候选列表。但在实际实现和平均情况下，由于我们一旦找到满足条件的候选词就会返回，并且候选列表不会特别长（除非有很多单词共享相同模式且只差一个字母），所以搜索通常很快。
• 空间复杂度：O(N * L)，用于存储所有模式及其对应的单词列表。

示例推演

以示例为例：

• buildDict(["hello", "leetcode"]):
  • 对于 "hello"，生成模式：*ello, h*llo, he*lo, hel*o, hell*，每个都映射到列表 ["hello"]。
  • 对于 "leetcode"，生成模式：*eetcode, l*etcode, ... 等，每个映射到 ["leetcode"]。
• search("hhllo"):
  • 生成模式：*hllo, h*llo, hh*lo, hhl*o, hhll*。
  • 检查模式 h*llo，在哈希表中存在，对应列表为 ["hello"]。
  • 列表中的 "hello" 长度与 "hhllo" 相同，且 "hello" != "hhllo"，因此返回 true。
• search("hello"):
  • 生成模式：*ello, h*llo, he*lo, hel*o, hell*。
  • 检查模式 *ello，在哈希表中存在，对应列表为 ["hello"]。
  • 列表中的 "hello" 与 "hello" 完全相同，不满足条件，继续检查。
  • 检查其他模式，情况类似，列表中唯一的候选词就是 "hello" 本身，因此始终不满足 candidate != searchWord 的条件，最终返回 false。

这种利用哈希表预处理通配符模式的方法，巧妙地将“恰好一个字符不同”的匹配问题，转换为了模式查找问题，从而实现了高效的搜索。