- 标签：深度优先搜索、设计、字典树、字符串
- 难度：中等
题目大意
#
要求：设计一个数据结构，支持「添加新单词」和「查找字符串是否与任何先前添加的字符串匹配」。
实现词典类 WordDictionary：
WordDictionary() 初始化词典对象。void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 True；否则，返回 False。word 中可能包含一些 .，每个 . 都可以表示任何一个字母。
解题思路
#
使用前缀树（字典树）。具体做法如下：
- 初始化词典对象时，构造一棵字典树。
- 添加
word 时，将 word 插入到字典树中。
- 搜索
word 时：
- 如果遇到
.，则递归匹配当前节点所有子节点，并依次向下查找。匹配到了，则返回 True，否则返回 False。
- 如果遇到其他小写字母，则按
word 顺序匹配节点。
- 如果当前节点为
word 的结尾，则放回 True。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.children = dict()
self.isEnd = False
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
cur = self
for ch in word:
if ch not in cur.children:
cur.children[ch] = Trie()
cur = cur.children[ch]
cur.isEnd = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
def dfs(index, node) -> bool:
if index == len(word):
return node.isEnd
ch = word[index]
if ch == '.':
for child in node.children.values():
if child is not None and dfs(index + 1, child):
return True
else:
if ch not in node.children:
return False
child = node.children[ch]
if child is not None and dfs(index + 1, child):
return True
return False
return dfs(0, self)
class WordDictionary:
def __init__(self):
self.trie_tree = Trie()
def addWord(self, word: str) -> None:
self.trie_tree.insert(word)
def search(self, word: str) -> bool:
return self.trie_tree.search(word)
|