实现一个魔法字典

我将为你讲解“实现一个魔法字典”这道题目。这个题目结合了哈希表与字符串处理，考察如何设计一个能支持“模糊匹配”查询的数据结构。

题目描述

设计一个名为 MagicDictionary 的字典类，它包含以下方法：

1. buildDict(String[] dictionary)：使用给定的字符串字典初始化数据结构。
2. search(String searchWord)：判断能否只修改一个字符，将 searchWord 变成字典中的某个字符串。如果可以，返回 true；否则返回 false。

注意：字典中的字符串可能重复，但所有字符串长度相同。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

解题思路

这道题的核心在于如何高效地判断“只差一个字符”。一个直观的想法是，对于每个搜索词，我们枚举修改它的每一个位置（共 L 个位置，L 是单词长度），每个位置尝试替换为其他 25 个字母（因为必须修改，且原字符本身不算），然后检查新词是否在字典中。但这样每次搜索的时间复杂度是 O(L * 25 * L)（因为每次构建新字符串需要 O(L)），最坏情况下可能达到 O(25L^2)。虽然可行，但我们可以进一步优化。

一个更巧妙的思路是使用哈希表对字典中的单词进行“广义邻居”预处理：

• 将每个单词的每个位置依次替换为一个通配符（例如 #），生成一个“模式”（pattern）。
• 例如单词 "hello" 可以生成模式 "#ello"、"h#llo"、"he#lo"、"hel#o"、"hell#"。
• 用哈希表存储每个模式出现的次数，以及原始单词是什么。
• 当搜索时，同样对搜索词生成所有模式，检查哈希表中是否存在且不是原始单词完全匹配的模式。

这个方法的优势在于预处理后，每次搜索只需 O(L) 时间生成模式并进行常数次哈希查找。

详细解题步骤

下面我分步详细讲解实现过程。

步骤 1：数据结构设计

我们需要一个哈希表来存储“模式”到“原始单词列表”的映射。因为可能有多个原始单词生成同一个模式，所以我们用哈希表 Map<String, List<String>> patterns，其中键是模式（如 "h#llo"），值是对应原始单词的列表。

步骤 2：buildDict 方法实现

1. 遍历字典中的每个单词 word。
2. 对于每个位置 i（从 0 到 L-1，L 是单词长度）：
   • 将 word 的第 i 个字符替换为通配符 '#'，生成模式 pattern。
   • 在哈希表 patterns 中，将 word 添加到 pattern 对应的列表中。
3. 注意：如果字典中有重复单词，同一个模式会多次添加相同单词，但这不影响结果，因为搜索时我们会比较原始单词是否与搜索词完全相同。

时间复杂度：O(N * L)，其中 N 是字典大小，L 是单词长度。

步骤 3：search 方法实现

1. 获取搜索词 searchWord 的长度 L。
2. 对于每个位置 i（从 0 到 L-1）：
   • 生成模式：将 searchWord 的第 i 个字符替换为 '#'，得到 pattern。
   • 检查 pattern 是否在 patterns 中：
     • 如果存在，遍历该模式对应的原始单词列表：
       • 如果存在一个原始单词 origin，满足 origin 与 searchWord 不相等，但只在位置 i 不同，则返回 true。
       • 注意：因为我们生成模式时是用通配符替换了位置 i，所以如果原始单词和搜索词在位置 i 的字符不同，但在其他位置完全相同，那么它们就恰好只差这一个字符。
3. 如果遍历完所有位置都没有找到满足条件的原始单词，则返回 false。

关键点：

• 为什么需要检查 origin != searchWord？因为如果原始单词和搜索词完全相同，那么不需要修改任何字符就能匹配，但题目要求必须修改一个字符，所以这种情况不符合条件。
• 为什么只差一个字符就能保证？因为模式已经确保了除位置 i 外其他字符完全相同，所以如果 origin 和 searchWord 在位置 i 的字符不同，它们就恰好只差一个字符。

时间复杂度：O(L^2)，因为生成每个模式需要 O(L) 时间，共有 L 个模式。但通常 L 较小，可以视为 O(L) 的常数倍。

代码实现

以下是基于上述思路的 Java 实现：

class MagicDictionary {
    private Map<String, List<String>> patterns;

    public MagicDictionary() {
        patterns = new HashMap<>();
    }
    
    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            char[] arr = word.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                char originalChar = arr[i];
                arr[i] = '#';
                String pattern = new String(arr);
                patterns.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
                arr[i] = originalChar; // 恢复原字符，供下一轮使用
            }
        }
    }
    
    public boolean search(String searchWord) {
        char[] arr = searchWord.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            char originalChar = arr[i];
            arr[i] = '#';
            String pattern = new String(arr);
            if (patterns.containsKey(pattern)) {
                for (String origin : patterns.get(pattern)) {
                    // 必须满足：原始单词与搜索词不同，且只差一个字符
                    if (!origin.equals(searchWord) && origin.length() == searchWord.length()) {
                        // 由于模式匹配已经保证了除位置 i 外其他字符相同，所以只需比较长度即可确认
                        // 注意：实际上因为模式是替换了位置 i，所以 origin 和 searchWord 在位置 i 的字符必然不同
                        // 但其他位置相同，所以 origin 和 searchWord 确实只差一个字符
                        return true;
                    }
                }
            }
            arr[i] = originalChar;
        }
        return false;
    }
}

示例运行

以题目示例为例：

1. buildDict(["hello", "leetcode"])：

   • 对于 "hello"，生成模式："#ello"、"h#llo"、"he#lo"、"hel#o"、"hell#"，每个模式对应的列表中都添加 "hello"。
   • 对于 "leetcode"，同样生成 8 个模式，每个模式添加 "leetcode"。

2. search("hhllo")：

   • 生成模式："#hllo"、"h#llo"、"hh#lo"、"hhl#o"、"hhll#"。
   • 当生成到 "h#llo" 时，哈希表中存在这个模式，对应的原始单词列表为 ["hello"]。
   • 比较 "hello" 和 "hhllo"，它们长度相同，且不相等，满足条件，因此返回 true。

复杂度分析

• 时间复杂度：
  • buildDict：O(N * L)，其中 N 是字典单词数，L 是单词长度。
  • search：O(L^2)，因为生成每个模式需要 O(L) 时间，但通常 L 较小，可视为 O(L)。
• 空间复杂度：O(N * L)，存储所有模式需要 N * L 个键值对（每个单词生成 L 个模式）。

优化与扩展

1. 优化搜索检查：在 search 中，我们可以提前判断原始单词与搜索词的长度是否相同，避免不必要的比较。
2. 处理重复单词：如果字典中有重复单词，我们的实现中会在同一个模式列表中添加多次，但这不影响正确性，因为比较时会逐个检查。
3. 扩展为修改 k 个字符：此方法可以扩展为支持修改最多 k 个字符的模糊匹配，只需生成替换 k 个位置的通配符模式，但模式数量会组合爆炸，适合 k 较小的情况。

这个题目很好地展示了如何利用哈希表将模糊匹配问题转化为精确匹配问题，通过预处理加速查询。希望这个讲解能帮助你理解其设计思路和实现细节。