Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class TriesContacts {
static class Node {
HashMap<Character, Node> links = null;
boolean isFinish;
int count;
public Node() {
links = new HashMap<>();
isFinish = false;
}
}
static class Trie {
Node root;
Trie() {
root = new Node();
}
public void addData(String data) {
Node current = root;
Character currentChar = ' ';
current.count++;
for (int i = 0; i <= data.length(); i++) {
if (i == data.length()) {
current.isFinish = true;
break;
}
currentChar = data.charAt(i);
if (current.links.containsKey(currentChar)) {
current = current.links.get(currentChar);
} else {
current.links.put(currentChar, new Node());
current = current.links.get(currentChar);
}
}
}
public int findPartial(String data, Node current) {
if (data.isEmpty()) {
return current.count;
}
char first = data.charAt(0);
return current.links.containsKey(first) ? findPartial(data.substring(1), current.links.get(first)) : 0;
}
}
public static int findCount(Node root) {
int count = 0;
if (root.isFinish) {
count++;
}
if (root.links != null) {
for (Map.Entry<Character, Node> entry : root.links.entrySet()) {
count += findCount(entry.getValue());
}
}
return count;
}
public TriesContacts() {
}
static class Command {
public String op;
public String data;
public Command(String op, String data) {
this.op = op;
this.data = data;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Trie trie = new Trie();
ArrayList<Command> commands = new ArrayList<>();
for (int a0 = 0; a0 < n; a0++) {
String op = in.next();
String contact = in.next();
commands.add(new Command(op, contact));
}
for (int index = 0; index < commands.size(); index++) {
if (commands.get(index).op.equals("add")) {
trie.addData(commands.get(index).data);
} else if (commands.get(index).op.equals("find")) {
int count = trie.findPartial(commands.get(index).data, trie.root);
System.out.println(count);
} else {
System.out.println("invalid input");
}
}
in.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.