LeetCode 题解工作台
实现一个魔法字典
设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中 一个 字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。 实现 MagicDictionary 类： MagicDictionary() 初始化对象 void buildD…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以使用前缀树来存储字典中的所有单词，然后对于每个搜索的单词，我们使用深度优先搜索的方法，具体地，我们从前缀树的根节点开始，对于当前遍历到的字母，我们首先判断是否存在与其相同的子节点，如果存在，则继续向下遍历，否则我们需要判断是否还有剩余的修改次数，如果没有，则说明无法匹配，返回 false。如果有剩余的修改次数，我们可以尝试对当前的字母进行修改，然后继续向下遍历，如果当前的字母修改后对应的子…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
实现 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
提示：
1 <= dictionary.length <= 1001 <= dictionary[i].length <= 100dictionary[i]仅由小写英文字母组成dictionary中的所有字符串 互不相同1 <= searchWord.length <= 100searchWord仅由小写英文字母组成buildDict仅在search之前调用一次- 最多调用
100次search
解题思路
方法一：前缀树 + DFS
我们可以使用前缀树来存储字典中的所有单词，然后对于每个搜索的单词，我们使用深度优先搜索的方法，具体地，我们从前缀树的根节点开始，对于当前遍历到的字母，我们首先判断是否存在与其相同的子节点，如果存在，则继续向下遍历，否则我们需要判断是否还有剩余的修改次数，如果没有，则说明无法匹配，返回 false。如果有剩余的修改次数，我们可以尝试对当前的字母进行修改，然后继续向下遍历，如果当前的字母修改后对应的子节点存在，则说明可以匹配，否则说明无法匹配，返回 false。如果我们遍历到了单词的结尾，且修改次数恰好为 1，那么说明可以匹配，返回 true。
时间复杂度 ，空间复杂度 ，其中 和 分别是字典中的单词数量和单词的平均长度，而 是搜索的单词数量。另外 表示字符集的大小，这里字符集为小写英文字母，因此 。
class Trie:
__slots__ = "children", "is_end"
def __init__(self):
self.children: List[Optional[Trie]] = [None] * 26
self.is_end = False
def insert(self, w: str) -> None:
node = self
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
def search(self, w: str) -> bool:
def dfs(i: int, node: Optional[Trie], diff: int) -> bool:
if i == len(w):
return diff == 1 and node.is_end
j = ord(w[i]) - ord("a")
if node.children[j] and dfs(i + 1, node.children[j], diff):
return True
return diff == 0 and any(
node.children[k] and dfs(i + 1, node.children[k], 1)
for k in range(26)
if k != j
)
return dfs(0, self, 0)
class MagicDictionary:
def __init__(self):
self.trie = Trie()
def buildDict(self, dictionary: List[str]) -> None:
for w in dictionary:
self.trie.insert(w)
def search(self, searchWord: str) -> bool:
return self.trie.search(searchWord)
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dictionary)
# param_2 = obj.search(searchWord)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an approach that efficiently handles multiple search calls after a single buildDict.
- question_mark
Ensure the candidate is considering both time and space complexities when implementing the solution.
- question_mark
Evaluate the candidate's ability to balance simplicity with performance, especially for string comparison and hash table usage.
常见陷阱
外企场景- error
Overcomplicating the search logic by checking all character permutations instead of focusing on one-character changes.
- error
Using inefficient data structures that result in slower lookups for large dictionaries.
- error
Ignoring edge cases such as words that are too short or when no valid word can be matched after modification.
进阶变体
外企场景- arrow_right_alt
Allowing multiple character changes in the search (e.g., two or more changes).
- arrow_right_alt
Supporting wildcard searches where multiple characters may change.
- arrow_right_alt
Optimizing further for large-scale dictionaries with millions of entries.