forked from algorithm020/algorithm020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTrie.java
More file actions
72 lines (64 loc) · 2 KB
/
Copy pathTrie.java
File metadata and controls
72 lines (64 loc) · 2 KB
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
package algorithm;
/**
* 208. 实现 Trie (前缀树)
* 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
* *********************************************************************************************************************
* 示例:
* 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
* *********************************************************************************************************************
* 208. Implement Trie (Prefix Tree)
**/
public class Trie {
private boolean isEnd;
private Trie[] next;
/**
* Initialize your data structure here.
*/
public Trie() {
isEnd = false;
next = new Trie[26];
}
/**
* Inserts a word into the trie.
*/
public void insert(String word) {
if (word == null || word.length() == 0) return;
Trie curr = this;
char[] words = word.toCharArray();
for (int i = 0; i < words.length; i++) {
int n = words[i] - 'a';
if (curr.next[n] == null) curr.next[n] = new Trie();
curr = curr.next[n];
}
curr.isEnd = true;
}
/**
* Returns if the word is in the trie.
*/
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String prefix) {
Trie node = searchPrefix(prefix);
return node != null;
}
private Trie searchPrefix(String word) {
Trie node = this;
char[] words = word.toCharArray();
for (int i = 0; i < words.length; i++) {
node = node.next[words[i] - 'a'];
if (node == null) return null;
}
return node;
}
}