题目描述
这是 LeetCode 上的 676. 实现一个魔法字典 ，难度为 中等。
Tag : 「字典树」、「DFS」
设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
实现 MagicDictionary 类：
-
MagicDictionary()初始化对象 -
void buildDict(String[] dictionary)使用字符串数组dictionary设定该数据结构，dictionary中的字符串互不相同 -
bool search(String searchWord)给定一个字符串searchWord，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回true；否则，返回false。
示例：
输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]
解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False
提示：
-
dictionary[i]仅由小写英文字母组成 -
dictionary中的所有字符串 互不相同 -
searchWord仅由小写英文字母组成 -
buildDict仅在search之前调用一次 - 最多调用
次
search
Trie + DFS
为了方便，我们令 dictionary 为 ss，令 searchWord 为 s。
整体题意：给定字符串 s，问能否存在替换掉 s 中的某个字符，使得新字符串出现在 ss 数组中。
考虑如何使用「字典树/Trie」求解该问题：
buildDict操作：我们可以将所有的存入字典树中，方便后续检索；
search操作：设计递归函数boolean query(String s, int idx, int p, int limit)，其中s为待检索的字符串，idx为当前处理到字符串s的哪一位，p为当前搜索到字典树的索引编号（起始有），
limit为当前剩余的替换字符次数，根据题意，limit固定为，含义为必须替换掉
s的一个字符。
对于而言，我们可以枚举新字符串在当前位置是何种字符（
个选择），若当前枚举到的字符与
爆搜过程中替换次数为负数直接剪枝，当爆搜到结尾位置，再检查当前的字典树索引是否为单词结尾节点（对应查询数组
ss中是否存在该字符串），以及剩余的替换次数limit是否为。
不了解「Trie / 字典树」的同学可以看前置 🧀：字典树入门。里面通过图例展示了字典树基本形态，以及提供了「数组实现」和「TrieNode 实现」两种方式，还有「数组大小估算方式」和「Trie 应用面」介绍
代码：
class MagicDictionary {
int N = 100 * 100, M = 26, idx = 0;
int[][] tr = new int[N][M];
boolean[] isEnd = new boolean[N * M];
void add(String s) {
int p = 0;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
}
isEnd[p] = true;
}
boolean query(String s, int idx, int p, int limit) {
if (limit < 0) return false;
if (idx == s.length()) return isEnd[p] && limit == 0;
int u = s.charAt(idx) - 'a';
for (int i = 0; i < 26; i++) {
if (tr[p][i] == 0) continue;
if (query(s, idx + 1, tr[p][i], i == u ? limit : limit - 1)) return true;
}
return false;
}
public void buildDict(String[] ss) {
for (String s : ss) add(s);
}
public boolean search(String s) {
return query(s, 0, 0, 1);
}
}
- 时间复杂度：
buildDict操作需要将所有字符存入Trie，复杂度为；
search操作在不考虑limit以及字典树中最多只有个方案，其中
为搜索字符串的最大长度
- 空间复杂度：
，其中
为存入
Trie的最大方案数，
最后
这是我们「刷穿 LeetCode」系列文章的第 No.676 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
本文由mdnice多平台发布
