友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
208. 实现 Trie (前缀树)
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
-
Trie()初始化前缀树对象。 -
void insert(String word)向前缀树中插入字符串word。 -
boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。 -
boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
-
1 <= word.length, prefix.length <= 2000 -
word和prefix仅由小写英文字母组成 -
insert、search和startsWith调用次数 总计 不超过3 * 104次
思路分析
没想到 Trie Tree 实现起来一点也不复杂！
思考题：如何实现一个工业级的 Trie Tree？
-
一刷
-
二刷
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/**
* Runtime: 69 ms, faster than 11.59% of Java online submissions for Implement Trie (Prefix Tree).
*
* Memory Usage: 62.6 MB, less than 5.77% of Java online submissions for Implement Trie (Prefix Tree).
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-26 19:47
*/
class Trie {
private int ALPHABET_SIZE = 26;
class TrieNode {
private TrieNode[] alphabet;
private boolean isEnd;
public TrieNode() {
this.alphabet = new TrieNode[ALPHABET_SIZE];
Arrays.fill(this.alphabet, null);
this.isEnd = false;
}
}
private TrieNode[] root;
/**
* Initialize your data structure here.
*/
public Trie() {
this.root = new TrieNode[ALPHABET_SIZE];
Arrays.fill(this.root, null);
}
/**
* Inserts a word into the trie.
*/
public void insert(String word) {
char[] chars = word.toCharArray();
TrieNode[] current = this.root;
for (int i = 0; i < chars.length; i++) {
int index = chars[i] - 'a';
if (Objects.isNull(current[index])) {
current[index] = new TrieNode();
}
if (i == chars.length - 1) {
current[index].isEnd = true;
}
current = current[index].alphabet;
}
}
/**
* Returns if the word is in the trie.
*/
public boolean search(String word) {
char[] chars = word.toCharArray();
TrieNode[] current = this.root;
for (int i = 0; i < chars.length; i++) {
int index = chars[i] - 'a';
if (Objects.isNull(current[index])) {
return false;
}
if (i == chars.length - 1) {
return current[index].isEnd;
}
current = current[index].alphabet;
}
return false;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String prefix) {
char[] chars = prefix.toCharArray();
TrieNode[] current = this.root;
for (int i = 0; i < chars.length; i++) {
int index = chars[i] - 'a';
if (Objects.isNull(current[index])) {
return false;
}
current = current[index].alphabet;
}
return true;
}
}
private void test() {
Trie trie = new Trie();
trie.insert("apple");
System.out.println(trie.search("apple"));
System.out.println(!trie.search("app"));
System.out.println(trie.startsWith("app"));
trie.insert("app");
System.out.println(trie.search("app"));
}
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
/**
* 没想到竟然一次通过，😁
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-02 19:42:48
*/
class Trie {
private Map<Character, Node> trie;
public Trie() {
trie = new HashMap<>();
}
public void insert(String word) {
Map<Character, Node> curr = trie;
Node node = null;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
node = curr.get(c);
if (node == null) {
node = new Node(c);
curr.put(c, node);
}
curr = node.children;
}
node.isEnd = true;
}
public boolean search(String word) {
Node node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private Node searchPrefix(String word) {
Map<Character, Node> curr = trie;
Node node = null;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
node = curr.get(c);
if (node == null) {
return null;
}
curr = node.children;
}
return node;
}
private static class Node {
char data;
boolean isEnd;
Map<Character, Node> children = new HashMap<>();
public Node(char data) {
this.data = data;
}
}
}