LeetCode 题解工作台
添加与搜索单词 - 数据结构设计
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 实现词典类 WordDictionary ： WordDictionary() 初始化词典对象 void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配 bool search…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
class Trie: def __init__(self):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
WordDictionary()初始化词典对象void addWord(word)将word添加到数据结构中，之后可以对它进行匹配bool search(word)如果数据结构中存在字符串与word匹配，则返回true；否则，返回false。word中可能包含一些'.'，每个.都可以表示任何一个字母。
示例：
输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]
解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True
提示：
1 <= word.length <= 25addWord中的word由小写英文字母组成search中的word由 '.' 或小写英文字母组成- 最多调用
104次addWord和search
解题思路
方法一
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class WordDictionary:
def __init__(self):
self.trie = Trie()
def addWord(self, word: str) -> None:
node = self.trie
for c in word:
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, word: str) -> bool:
def search(word, node):
for i in range(len(word)):
c = word[i]
idx = ord(c) - ord('a')
if c != '.' and node.children[idx] is None:
return False
if c == '.':
for child in node.children:
if child is not None and search(word[i + 1 :], child):
return True
return False
node = node.children[idx]
return node.is_end
return search(word, self.trie)
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on word length L and Trie branching; addWord is O(L), search is O(26^k * L) in worst case with k wildcards. Space complexity is O(N*L) for storing N words, considering shared prefixes in Trie nodes. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for efficient prefix storage and DFS handling of wildcards.
- question_mark
Check if you handle '.' correctly with recursive exploration.
- question_mark
Expect awareness of Trie node memory usage and early pruning for performance.
常见陷阱
外企场景- error
Not handling '.' correctly can miss valid matches or overcount paths.
- error
Failing to mark the end of words leads to false positives when searching prefixes.
- error
Inefficient DFS without pruning may timeout with multiple wildcard searches.
进阶变体
外企场景- arrow_right_alt
Restrict to exact matches only, removing wildcard support.
- arrow_right_alt
Allow arbitrary number of wildcards instead of a max of 2.
- arrow_right_alt
Implement with a hash map of word lengths for faster lookup without Trie.