LeetCode 676. 实现一个魔法字典

约 5 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
字符串 哈希表 深度优先搜索 设计 字典树

题目描述

✅ 676. 实现一个魔法字典

image-20260929104513041

image-20260929104513194

题意分析

先构建一个单词字典，再判断查询词能否通过恰好替换一个字符变成字典中的某个单词。不能不修改，也不能插入或删除字符，因此命中的单词必须与查询词等长且恰好有一处不同。

输入只包含小写英文字母。可以直接枚举唯一修改的位置，以及该位置替换成什么字母，再查询字典是否包含生成的候选。

解法：枚举替换 + 哈希集合

核心思路

[!blue]

构建时，把全部单词放入哈希集合。查询时，将查询词转为可修改的字符数组；Go 中的小写英文字母可直接按字节处理。

枚举位置 i，记住原字符 old，再枚举 a..z 中不同于 old 的 25 个字母。每次只替换这一位，构造候选字符串并查集合，命中就返回 true。候选长度不变，其他位置未改，并且替换字母与原字母不同，所以命中一定对应恰好一次合法修改。

反过来，如果存在可行修改，它必然有一个确定位置和一个不同的新字母，这两个选择一定会被枚举到。因此全部候选都没有命中时，可以返回 false。

一个位置尝试结束后，要恢复原字符再处理下一个位置，使每轮仍然基于最初的查询词。字典中是否包含原查询词本身不能直接决定答案：原词对应零次修改，应排除，但集合里仍可能有另一个单词符合恰好一次修改。

解题步骤

  1. buildDict 将字典单词加入哈希集合；题目保证它在查询前只调用一次。
  2. 查询时复制为可修改的字符或字节数组，逐个选择待替换位置。
  3. 保存该位置原字符，尝试另外 25 个小写字母，每次生成候选并查集合。
  4. 命中候选则返回 true；当前位置全部尝试后恢复原字符。
  5. 所有位置都处理完仍未命中，返回 false。

代码实现

class MagicDictionary {
    private final Set<String> set = new HashSet<>();

    public void buildDict(String[] dictionary) {
        for (String w : dictionary) {
            set.add(w);
        }
    }

    public boolean search(String searchWord) {
        char[] s = searchWord.toCharArray();

        // 每个位置尝试完后恢复原字符，使下一轮仍基于原查询词。
        for (int i = 0; i < s.length; i++) {
            char old = s[i];

            for (char ch = 'a'; ch <= 'z'; ch++) {
                // 必须恰好修改一位，原字符不作为替换候选。
                if (ch == old) {
                    continue;
                }

                s[i] = ch;

                if (set.contains(new String(s))) {
                    s[i] = old;

                    return true;
                }
            }

            s[i] = old;
        }

        return false;
    }
}

type MagicDictionary struct {
    set map[string]struct{}
}

func Constructor() MagicDictionary {
    return MagicDictionary{set: make(map[string]struct{})}
}

func (m *MagicDictionary) BuildDict(dictionary []string) {
    for _, w := range dictionary {
        m.set[w] = struct{}{}
    }
}

func (m *MagicDictionary) Search(searchWord string) bool {
    b := []byte(searchWord)
    // 每个位置尝试完后恢复原字符，使下一轮仍基于原查询词。
    for i := 0; i < len(b); i++ {
        old := b[i]
        for ch := byte('a'); ch <= byte('z'); ch++ {
            // 必须恰好修改一位，原字符不作为替换候选。
            if ch == old {
                continue
            }
            b[i] = ch
            if _, ok := m.set[string(b)]; ok {
                b[i] = old
                return true
            }
        }
        b[i] = old
    }
    return false
}

复杂度分析

设字典总字符数为 D，查询词长度为 L。

  • 时间复杂度：构建期望 $O(D)$。每次查询生成 25L 个候选，每个候选的构造和字符串哈希需要 $O(L)$，所以查询期望为 $O(26L^2)$，不能只按枚举次数计算。
  • 空间复杂度：字典内容及索引为 $O(D)$；单次查询的字符数组和当前候选为 $O(L)$ 临时空间。

关键点总结

[!green]

  • 唯一修改可由“位置、新字母”完整描述，穷举这两个维度即可覆盖全部合法候选。
  • 替换字母必须不同于原字母，保证修改次数恰好为一。
  • 每个位置结束后恢复字符，保证候选之间不会累积多次修改。
  • 原词存在不代表成功，也不能据此直接失败，仍需寻找只差一处的另一单词。

易错点总结

[!yellow]

  • 直接判断原词是否在集合中，实际上检查的是零次修改。
  • 看到原词已存在就返回 false，会漏掉同时存在的其他合法候选。
  • 不恢复上一位置的字符，后续候选可能已经改变两处或更多位置。
  • 枚举时包含原字母，会把没有变化的原词误当作恰好修改一次。
  • 将字符串集合查询视为无条件的常数成本，忽略每个新候选的复制和哈希扫描。

相似题目

题目 难度 关联与区别
211. 添加与搜索单词 - 数据结构设计 中等 同样在Trie中进行带分支的匹配，原题通配符位置由模式给定，本题自行消耗恰好一次替换。
161. 相隔为 1 的编辑距离 中等 都限制恰好一次编辑，原题允许插入删除，本题只能替换一个字符且需命中字典。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/58573618
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！