Last active
January 30, 2017 10:44
-
-
Save rohit012/e7fd373426c62a44740f067bfd7c6dfe to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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