友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
211. 添加与搜索单词 - 数据结构设计
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 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 <= 25 -
addWord中的word由小写英文字母组成 -
search中的word由 '.' 或小写英文字母组成 -
最多调用
104次addWord和search
思路分析
前缀树。需要处理通配符的情况，尤其要注意结尾字符的处理。
-
一刷
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
60
61
62
63
64
65
66
67
68
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-30 00:08:59
*/
static class WordDictionary {
private WordDictionary[] letters;
private boolean end = false;
public WordDictionary() {
letters = new WordDictionary[26];
}
public void addWord(String word) {
char[] chars = word.toCharArray();
WordDictionary current = this;
for (int i = 0; i < chars.length; i++) {
if (current.letters[chars[i] - 'a'] == null) {
current.letters[chars[i] - 'a'] = new WordDictionary();
}
current = current.letters[chars[i] - 'a'];
if (i == chars.length - 1) {
current.end = true;
}
}
}
public boolean search(String word) {
char[] chars = word.toCharArray();
return backtrack(chars, 0, this);
}
private boolean backtrack(char[] chars, int index,
WordDictionary current) {
if (index == chars.length) {
return true;
}
if (chars[index] == '.') {
for (int i = 0; i < 26; i++) {
if (current.letters[i] == null) {
continue;
}
if (index == chars.length - 1) {
if (current.letters[i].end) {
return true;
} else {
continue;
}
}
boolean ok = backtrack(chars, index + 1, current.letters[i]);
if (ok) {
return true;
}
}
return false;
} else {
WordDictionary next = current.letters[chars[index] - 'a'];
if (next == null) {
return false;
} else {
if (index == chars.length - 1) {
return next.end;
}
return backtrack(chars, index + 1, next);
}
}
}
}