-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTrieST.java
More file actions
160 lines (134 loc) · 4.27 KB
/
Copy pathTrieST.java
File metadata and controls
160 lines (134 loc) · 4.27 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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
/**
* Created by Mofeng on 2017/6/1.
*/
public class TrieST<Value> {
private static int R = 256;
private Node root;
private int n;
private static class Node {
private Object val;
private Node[] next = new Node[R];
}
public TrieST() {
}
public Value get(String key) {
Node x = get(root, key, 0);
if (x == null) return null;
return (Value)x.val;
}
public boolean contains(String key) {
return get(key) != null;
}
private Node get(Node x, String key, int d) {
if (x == null) return null;
if (d == key.length()) return x;
char c = key.charAt(d);
return get(x.next[c], key, d+1);
}
public void put(String key, Value val) {
root = put(root, key, val, 0);
}
private Node put(Node x, String key, Value val, int d) {
if (x == null) x = new Node();
if (d == key.length()) {
if (x.val == null)
n++;
x.val = val; return x;
}
char c = key.charAt(d);
x.next[c] = put(x.next[c], key, val, d+1);
return x;
}
public int size() {
return n;
}
public boolean isEmpty() {
return size() == 0;
}
public Iterable<String> keys() {
return keysWithPrefix("");
}
public Iterable<String> keysWithPrefix(String pre) {
Queue<String> q = new Queue<String>();
collect(get(root, pre, 0), pre, q);
return q;
}
private void collect(Node x, String pre, Queue<String> q) {
if (x == null) return;
if (x.val != null) q.enqueue(pre);
for (char c = 0; c < R; c++)
collect(x.next[c], pre+c, q);
}
public Iterable<String> keysThatMatch(String pat) {
Queue<String> q = new Queue<String>();
collect(root, "", pat, q);
return q;
}
public void collect(Node x, String pre, String pat, Queue<String> q) {
int d = pre.length();
if (x == null) return;
if (d == pat.length() && x.val != null) q.enqueue(pre);
if (d == pat.length()) return ;
char next = pat.charAt(d);
for (char c = 0; c < R; c++)
if (next == '.' || next == c)
collect(x.next[c], pre+c, pat, q);
}
public String longestPrefixOf(String s) {
int length = search(root, s, 0, 0);
return s.substring(0, length);
}
private int search(Node x, String s, int d, int length) {
if (x == null) return length;
if (x.val != null) length =d;
if (d == s.length()) return length;
char c = s.charAt(d);
return search(x.next[c], s, d+1, length);
}
public void delelte(String key) {
root = delelte(root, key ,0);
}
private Node delelte(Node x, String key, int d) {
if (x == null) return null;
if (d == key.length())
x.val = null;
else
{
char c = key.charAt(d);
x.next[c] = delelte(x.next[c], key, d+1);
}
if (x.val != null) return x;
for (char c = 0; c < R; c++)
if (x.next[c] != null) return x;
return null;
}
public static void main(String[] args) {
TrieST<Integer> st = new TrieST<Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
if (st.size() < 100) {
StdOut.println("keys(\"\"):");
for (String key: st.keys())
StdOut.println(key + " " + st.get(key));
StdOut.println();
}
StdOut.println("longestPrefixOf(\"shellsort\")");
StdOut.println(st.longestPrefixOf("shellsort"));
StdOut.println();
StdOut.println("longestPrefixOf(\"quicksort\"):");
StdOut.println(st.longestPrefixOf("quicksort"));
StdOut.println();
StdOut.println("keysWithPrefix(\"shor\"):");
for (String s : st.keysWithPrefix("shor"))
StdOut.println(s);
StdOut.println();
StdOut.println("keysThatMatch(\".he.l.\"):");
for (String s : st.keysThatMatch(".he.l."))
StdOut.println(s);
}
}