-
Notifications
You must be signed in to change notification settings - Fork 0
/
Trie.java
60 lines (57 loc) · 1.39 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
import java.util.Scanner;
public class Trie {
public static String [] input;
public static int [] alph= new int[26];
public static void main(String[] args) {
Scanner in= new Scanner(System.in);
int n= in.nextInt();
input= new String[n];
for (int i = 0; i < n; i++) input[i]= in.next();
for (int i = 0; i < alph.length; i++) {
alph[i]= i;
}
node trie= new node();
for (int i = 0; i < input.length; i++) {
trie.add(0, i, input[i].toCharArray());
}
for (int i = 1; i <= 9; i++) {
System.out.println(trie.query(i));
}
}
static class node{
//size is how many words pass through me, id is what word i am related to the input
//term represents how many words end here
int size, id, term;
node [] children;
public node() {
size=0;
term=0;
children= new node[26];
}
//adds a word to my trie
public void add(int ind, int ii, char [] word) {
size++;
if(ind==word.length) {
term++;
id= ii;
return;
}
int c= word[ind]-'a';
if(children[c]==null) {
children[c]= new node();
}
children[c].add(ind+1, ii, word);
}
//finds the lexicographically kth string according to alph
String query(int k) {
if(term>=k) return input[id];
int tot= term;
for(int i: alph) {
if(children[i]==null) continue;
if(k<=tot+children[i].size) return children[i].query(k-tot);
tot+=children[i].size;
}
return null;
}
}
}