LeetCode LCR 064. 实现一个魔法字典

2026-03-28 HGNULB 约 10 分钟

文章信息 5 个分类 6 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 064. 实现一个魔法字典

题意分析

设计一个字典结构，先用一批互不相同的单词建好词库，之后反复回答同一个问题：能否把查询串中恰好一个字符换成另一个不同的字符，使它变成词库中的某个单词。

「恰好一个」是全部难点所在。它同时排除了两种情况：改动零个字符（查询串本身就在词库里，不算）和改动两个及以上。翻译成度量就是——存在一个词库单词，与查询串的汉明距离正好等于 1。距离为 0 不行，距离大于 1 也不行。

汉明距离这个说法本身还隐含了长度必须相同：只能替换字符，不能增删，所以长度不等的单词直接出局，不必比较。这一条把候选集合先按长度切了一刀。

约束里单词数与查询次数都在 100 到 $10^2$ 量级，单词长度不超过 100，字符集是小写字母。规模很小，说明可以为每个单词预处理出若干「变形」并全部存下来，用空间换查询时间，不必担心爆内存。

边界上要注意三处：查询串本身就在词库里时，如果没有第二个只差一位的单词，必须返回假；词库中可能存在两个只差一位的单词，此时用其中一个去查会命中另一个；查询串的长度可能与词库中任何单词都不同，此时必然返回假。

解法：哈希表统计状态

核心思路

暴力做法是每次查询都遍历整个词库，对每个等长单词逐位比较、统计不同字符的个数，看是否恰好为 1。单次查询 $O(N \cdot L)$，总代价 $O(Q \cdot N \cdot L)$。规模内能过，但没有把「建库」这个免费的预处理阶段利用起来。

瓶颈在于每次查询都要把词库整个扫一遍，而绝大多数单词甚至第一个字符就已经注定不匹配，比较的开销全部浪费。更本质的问题是：「差一位」这种关系无法用整串哈希直接查，因为整串一旦改动，哈希键就完全变了。

观察的切入点是把「差一位」显式化。若单词 w 与查询串 s 恰好在第 i 位不同，那么把两者的第 i 位都换成同一个占位符 * 之后，它们会变成完全相同的字符串。于是「存在差一位的单词」就等价于「存在某个位置 i，使得 s 的 i 位掩码形式出现在词库的掩码集合里」——一个可以用哈希精确匹配的问题。

由此定下状态定义：counter[p] 表示词库中有多少个单词能生成掩码 p；另用集合 words 记录词库原串。建库时对每个单词生成 $L$ 个掩码（依次把每一位换成 *），把计数累加上去。

查询时对 s 同样生成 $L$ 个掩码，逐个去查 counter。这里必须处理「距离为 0 不算」：若某掩码的计数为 1，命中的那个单词有可能就是 s 自己（当 s 恰在词库中时），此时距离是 0 不能算数；但只要计数大于 1，就一定存在除 s 之外的第二个单词共享这个掩码，距离必为 1。

于是判定条件收敛成两条：counter[p] > 1，或者 counter[p] == 1 且 s 本身不在词库中。任一掩码满足即返回真，全部落空返回假。这个条件维持的不变量是：只在能确认「命中的单词不是 s 自己」时才判定成功。

解题步骤

建库时同时维护两张表：原串集合 words 与掩码计数表 counter。原串集合是后面排除「距离为 0」的唯一依据，不能省。

对每个单词，逐位把该位替换成 * 生成掩码，counter 对应项加一。用 * 而不是某个字母做占位符，是因为它不属于小写字母集，绝不会与真实字符混淆造成误匹配。

掩码要对每一位都生成，共 $L$ 个。少生成一位，那一位上的差异就永远查不出来。

查询时用同一套规则给 s 生成 $L$ 个掩码，逐个查 counter。生成规则必须与建库时完全一致，占位符不同就全盘失配。

判定用 counter[p] > 1 || (counter[p] == 1 && !words.contains(s))。前半条覆盖「至少两个单词共享该掩码，其中必有一个不是 s」；后半条覆盖「只有一个单词共享该掩码，且 s 不在词库中，那么它必然不是 s」。

任一掩码判定成功就立刻返回真；全部掩码检查完仍未成功则返回假。长度不匹配的情况不需要特判，因为长度不同的单词生成的掩码长度也不同，天然不会碰撞。

以 buildDict(["hello", "leetcode"]) 后依次查询 "hello"、"hhllo"、"hell"、"leetcoded" 走一遍：建库时 "hello" 生成 *ello、h*llo、he*lo、hel*o、hell* 五个掩码，各计数 1；"leetcode" 生成八个掩码，各计数 1；words = {"hello", "leetcode"}。查询 "hello"：它的五个掩码与建库时完全一致，每个计数都是 1，而 words 里确实有 "hello"，所以 counter == 1 && !contains 不成立、counter > 1 也不成立，五个掩码全部落空，返回 false——正确，因为这是距离 0。查询 "hhllo"：掩码 *hllo 计数 0 跳过；掩码 h*llo 计数为 1，且 "hhllo" 不在 words 中，条件成立，立即返回 true——命中的正是 "hello"，距离 1。查询 "hell"：长度 4，生成的四个掩码长度都是 4，而词库掩码长度分别是 5 和 8，计数全为 0，返回 false。查询 "leetcoded"：长度 9，同理全部落空，返回 false。

代码实现

class MagicDictionary {
    private Set<String> words;
    private Map<String, Integer> counter;

    public MagicDictionary() {
        words = new HashSet<>();
        counter = new HashMap<>();
    }

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            words.add(word);
            for (String p : patterns(word)) {
                counter.put(p, counter.getOrDefault(p, 0) + 1);
            }
        }
    }

    public boolean search(String searchWord) {
        for (String p : patterns(searchWord)) {
            int cnt = counter.getOrDefault(p, 0);
            if (cnt > 1 || (cnt == 1 && !words.contains(searchWord))) {
                return true;
            }
        }
        return false;
    }

    private List<String> patterns(String word) {
        List<String> res = new ArrayList<>();
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; ++i) {
            char c = chars[i];
            chars[i] = '*';
            res.add(new String(chars));
            chars[i] = c;
        }
        return res;
    }
}

type MagicDictionary struct {
    words   map[string]bool
    counter map[string]int
}

func Constructor() MagicDictionary {
    return MagicDictionary{
        words:   make(map[string]bool),
        counter: make(map[string]int),
    }
}

func (this *MagicDictionary) BuildDict(dictionary []string) {
    for _, word := range dictionary {
        this.words[word] = true
        for _, p := range patterns(word) {
            this.counter[p]++
        }
    }
}

func (this *MagicDictionary) Search(searchWord string) bool {
    for _, p := range patterns(searchWord) {
        if this.counter[p] > 1 || (this.counter[p] == 1 && !this.words[searchWord]) {
            return true
        }
    }
    return false
}

func patterns(word string) []string {
    var res []string
    for i := 0; i < len(word); i++ {
        res = append(res, word[:i]+"*"+word[i+1:])
    }
    return res
}

复杂度分析

时间复杂度：建库 $O(N \cdot L^2)$，每个单词生成 $L$ 个掩码、每个掩码的构造与哈希各需 $O(L)$；单次查询 $O(L^2)$，同样是 $L$ 个掩码乘以每个掩码 $O(L)$ 的构造与查表开销，与词库规模无关。

空间复杂度：$O(N \cdot L^2)$，掩码计数表里存了 $N \cdot L$ 个长度为 $L$ 的字符串，原串集合的 $O(N \cdot L)$ 相比之下可以忽略。

关键点总结

「恰好差一位」无法用整串哈希直接查，但把差异位统一抹成占位符后，模糊匹配就被转化成了精确匹配。这个「掩码归一化」技巧在处理容错匹配、近似去重时都能复用。

占位符必须选在字符集之外。用小写字母当占位符会与真实字符撞车，制造出根本不存在的匹配。

用计数而不是布尔标记，是为了区分「只有查询串自己」和「还有别人」。当判定需要排除自身时，计数比存在性多携带的那一点信息正是关键。

建库阶段付出的额外空间换来了与词库规模无关的查询时间，这是典型的设计类题目取舍：查询次数多时优先压查询复杂度。

长度不等的单词无需特判，因为掩码长度不同天然不碰撞。让数据结构自己承担过滤，比手写一堆前置判断更不容易出错。

面试视角：主动点明「距离必须恰好为 1」这个陷阱，并说明你是用 counter > 1 与 words 集合两条件配合排除自身的，这一句往往就是这题的得分点。

面试视角：常见追问是「如果允许改动最多 $k$ 位怎么办」。此时掩码方案的组合数会膨胀到 $O(L^k)$ 不再划算，应改用 Trie 上带剩余修改次数的深度优先搜索，把状态从字符串换成「节点 + 剩余次数」。

易错点总结

错误写法：判定条件写成 counter[p] >= 1 就返回真。用例 buildDict(["hello"]) 后 search("hello") → 掩码 h*llo 计数为 1 于是返回 true，正确答案是 false，这是距离 0 不是距离 1。

错误写法：只用集合记录掩码是否出现，不记计数。用例 buildDict(["hello", "hallo"]) 后 search("hello") → 掩码 h*llo 只知道「出现过」，无法判断出现的是不是 "hello" 自己，若据此排除则返回 false，正确答案是 true（可以变成 "hallo"）。

错误写法：占位符用小写字母，比如统一换成 'a'。用例 buildDict(["hallo"]) 后 search("hello") → 查询串的掩码 hallo 与词库单词原串 "hallo" 撞成同一个键，本来只该是掩码层面的匹配被真实字符污染，在含 'a' 的数据上会造出虚假命中。

错误写法：生成掩码时漏掉首位或末位。用例 buildDict(["hello"]) 后 search("aello") → 差异在第 0 位，若掩码从下标 1 开始生成则查不到，返回 false，正确答案是 true。

错误写法：Java 版在 patterns 中改完 chars[i] 后忘记还原。用例 buildDict(["hello"]) → 第二个掩码变成 **llo、第三个变成 ***lo，掩码表整体错乱，此后所有查询结果都不可信。

错误写法：建库与查询使用不同的占位符（比如建库用 *、查询用 .）。用例 buildDict(["hello"]) 后 search("hhllo") → 两套键完全不相交，计数恒为 0，返回 false，正确答案是 true。

错误写法：先特判「查询串在词库中就直接返回 false」。用例 buildDict(["hello", "hallo"]) 后 search("hello") → 直接返回 false，但 "hello" 改一位可以变成 "hallo"，正确答案是 true。

错误写法：search 中对每个掩码都累加匹配数、最后统一判断。用例 buildDict(["hello", "hallo"]) 后 search("hxllo") → 掩码 h*llo 计数为 2，如果把它理解成「有两种改法」而要求恰好一种，就会误判为 false，正确答案是 true，题目只要求存在一种改法。

相似题目

题目	难度	考察点
676. 实现一个魔法字典	中等	与本题同题，可用来对照掩码哈希与 Trie 带容错搜索两种实现
211. 添加与搜索单词 - 数据结构设计	中等	通配符位置由查询串显式给出，无需自己枚举差异位
208. 实现 Trie (前缀树)	中等	只做精确与前缀查询，不涉及容错，是本题的结构基础
720. 词典中最长的单词	中等	判定沿整条路径累积，考察的是逐字符可达性而非单点差异
648. 单词替换	中等	匹配锚定在前缀且要取最短，靠首次命中提前退出而非计数排除
1268. 搜索推荐系统	中等	返回值从布尔变成候选列表，需要在节点上维护有序结果集
745. 前缀和后缀搜索	困难	同样靠构造复合键把双端约束压成一次哈希查询，键的设计更复杂