-
Notifications
You must be signed in to change notification settings - Fork 862
/
TriesContacts.java
121 lines (109 loc) · 2.45 KB
/
TriesContacts.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
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
/**
*
* Problem Statement-
* [Tries: Contacts](https://www.hackerrank.com/challenges/ctci-contacts/problem)
*
*/
package com.javaaid.hackerrank.solutions.tutorials.ctci;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @author Kanahaiya Gupta
*
*/
class TST<Value> {
private Node root;
private class Node {
private Value val;
private char c;
private Node left, mid, right;
}
public void put(String key, Value val) {
root = put(root, key, val, 0);
}
/**
* @param root2
* @param key
* @param val
* @param i
* @return
*/
private Node put(Node x, String key, Value val, int d) {
char c = key.charAt(d);
if (x == null) {
x = new Node();
x.c = c;
}
if (c < x.c)
x.left = put(x.left, key, val, d);
else if (c > x.c)
x.right = put(x.right, key, val, d);
else if (d < key.length() - 1)
x.mid = put(x.mid, key, val, d + 1);
else
x.val = val;
return x;
}
/**
* @param root2
* @param key
* @param i
* @return
*/
private Node get(Node x, String key, int d) {
if (x == null)
return null;
char c = key.charAt(d);
if (c < x.c)
return get(x.left, key, d);
else if (c > x.c)
return get(x.right, key, d);
else if (d < key.length() - 1)
return get(x.mid, key, d + 1);
else
return x;
}
/**
* @param root2
* @param string
* @param queue
*/
private void collect(Node x, StringBuilder prefix, Queue<String> q) {
if (x == null)
return;
collect(x.left, prefix, q);
if (x.val != null)
q.offer(prefix.toString() + x.c);
collect(x.mid, prefix.append(x.c), q);
prefix.deleteCharAt(prefix.length() - 1);
collect(x.right, prefix, q);
}
public Queue<String> keyWithPrefix(String prefix) {
Queue<String> queue = new LinkedList<String>();
Node x = get(root, prefix, 0);
if (x == null)
return queue;
if (x.val != null)
queue.offer(prefix);
collect(x.mid, new StringBuilder(prefix), queue);
return queue;
}
}
public class TriesContacts {
public static void main(String[] args) {
TST<Integer> tst = new TST<Integer>();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
String op = sc.next();
String name = sc.next();
if (op.equals("add")) {
tst.put(name, i);
} else {
System.out.println(tst.keyWithPrefix(name).size());
}
}
sc.close();
}
}