-
Notifications
You must be signed in to change notification settings - Fork 33
/
Trie.java
83 lines (73 loc) · 2.1 KB
/
Trie.java
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
package com.marcusmccurdy.trie;
import java.util.*;
import java.util.Map.Entry;
/**
*
* @author Marcus McCurdy <marcus.mccurdy@gmail.com>
*/
public class Trie {
protected final Map<Character, Trie> children;
protected String value;
protected boolean terminal = false;
public Trie() {
this(null);
}
private Trie(String value) {
this.value = value;
children = new HashMap<Character, Trie>();
}
protected void add(char c) {
String val;
if (this.value == null) {
val = Character.toString(c);
} else {
val = this.value + c;
}
children.put(c, new Trie(val));
}
public void insert(String word) {
if (word == null) {
throw new IllegalArgumentException("Cannot add null to a Trie");
}
Trie node = this;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) {
node.add(c);
}
node = node.children.get(c);
}
node.terminal = true;
}
public String find(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) {
return "";
}
node = node.children.get(c);
}
return node.value;
}
public Collection<String> autoComplete(String prefix) {
Trie node = this;
for (char c : prefix.toCharArray()) {
if (!node.children.containsKey(c)) {
return Collections.emptyList();
}
node = node.children.get(c);
}
return node.allPrefixes();
}
protected Collection<String> allPrefixes() {
List<String> results = new ArrayList<String>();
if (this.terminal) {
results.add(this.value);
}
for (Entry<Character, Trie> entry : children.entrySet()) {
Trie child = entry.getValue();
Collection<String> childPrefixes = child.allPrefixes();
results.addAll(childPrefixes);
}
return results;
}
}