LeetCode LCR 064. 实现一个魔法字典
题目描述
题意分析
先用词库建好字典，再判断每个查询串能否恰好替换一个字符后变成某个词库单词。不能增加或删除字符，替换后的字符也必须与原字符不同，所以目标单词需要与查询串长度相同，并且只在一个位置上不同。
查询串本身在词库中，并不直接说明成功或失败：它与自己没有差异，但词库里仍可能存在另一个只差一位的单词。题目保证词库内的单词互不相同，且
buildDict只在查询前调用一次。
解法：单字符通配签名与计数
核心思路
[!blue]
两个等长单词如果只在位置
i不同，将该位置都替换为*后，就会得到相同字符串。把这个只含一个*的字符串称为模式。因为输入仅有小写字母，*不会与原字符混淆；相同模式还会同时保证字符串长度和被遮住的位置一致。共享模式只能说明两个单词在其余位置完全相同，也就是至多差一个字符，不能直接推出恰好差一个。因此维护两张表：
counter[p]记录多少个词库单词能生成模式p，words保存完整的词库单词，用来判断查询串是否贡献了其中的一份计数。建库时，每个长度为
L的单词依次遮住各个位置，生成L个模式并累加计数。词库单词互不相同，同一单词不同位置的星号也不同，所以counter[p]正好是共享该模式的不同词库单词数。查询时生成同样的模式，并检查每个模式的计数
cnt：
cnt > 1：至少有两个不同词库单词共享该模式，其中必有一个不是查询串。其余位置相同、整串又不同，差异就只能在被遮住的那个位置，满足恰好替换一次。cnt == 1且查询串不在words中：唯一匹配的词库单词也不可能是查询串自身，同样恰好差一位。cnt == 0，或cnt == 1且查询串在词库中：没有可用的其他单词，这个模式不能判定成功，应继续检查其他位置。任意模式成功就返回真，全部失败才返回假。若确实存在只差一位的词库单词，遮住那个差异位置一定会遇到它，因此不会漏解；长度不同的单词生成的模式长度也不同，天然无法匹配。
Java 通过字符数组临时改一位、创建模式后立即还原，保证下一次仍只遮住一个位置；Go 每次用前缀、
*、后缀拼成新模式，实现相同的生成规则。
解题步骤
- 初始化完整词集合
words和模式计数表counter。- 建库时保存每个原词，并逐位生成单星模式、增加对应计数。
- 查询时按同样方式生成各位置的模式，读取
cnt。- 当
cnt > 1，或cnt == 1且查询串不在原词集合中时返回真；所有位置都不满足则返回假。
代码实现
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
}
复杂度分析
- 时间复杂度：设词库含
N个单词、最大长度为L。建库期望为 $O(NL^2)$：每词生成至多L个模式，模式构造与哈希按长度计费。长度为P的单次查询期望为 $O(P^2)$，与词库单词数量无关。- 空间复杂度：持久存储最坏为 $O(NL^2)$，至多保存
NL个长度不超过L的模式，另有原词集合。当前patterns一次性生成全部模式，单次查询还需要 $O(P^2)$ 临时空间。
关键点总结
[!green]
- 单星模式固定了长度、差异位置和其余全部字符，只把可能变化的一位隐藏起来。
- 模式存在只能证明至多差一位；计数与原词集合一起排除零次修改。
- 查询原词时不能直接拒绝，还要检查是否有另一单词共享某个模式。
- 单次建库和词库互异的题面保证，使模式计数可以直接按单词累加。
易错点总结
[!yellow]
- 只记录模式是否存在，会把查询串与自身的零差异误判为一次替换。
- 因为查询原词已存在就直接返回假，会漏掉它与其他词只差一位的情况。
- Java 生成一个模式后不还原字符，会让后续模式含多个星号，错误允许多处变化。
- 占位符必须在输入字母表之外，且建库与查询使用完全相同的生成规则。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 211. 添加与搜索单词 - 数据结构设计 | 中等 | 同样在Trie中进行带分支的匹配，原题通配符位置由模式给定，本题自行消耗恰好一次替换。 |
| 161. 相隔为 1 的编辑距离 | 中等 | 都限制恰好一次编辑，原题允许插入删除，本题只能替换一个字符且需命中字典。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！