Tries: Contacts HackerRank Solution

Tries: Contacts HackerRank Solution
Source : https://www.hackerrank.com/challenges/ctci-contacts

We're going to make our own Contacts application! The application must perform two types of operations:

1. add name, where is a string denoting a contact name. This must store as a new contact in the application.
2. find partial, where is a string denoting a partial name to search the application for. It must count the number of contacts starting with and print the count on a new line.

Given sequential add and find operations, perform each operation in order.

Input Format

The first line contains a single integer, , denoting the number of operations to perform.
Each line of the subsequent lines contains an operation in one of the two forms defined above.

Constraints

• It is guaranteed that and contain lowercase English letters only.
• The input doesn't have any duplicate for the operation.

Output Format

For each find partial operation, print the number of contact names starting with on a new line.

Sample Input

4add hackadd hackerrankfind hacfind hak

Sample Output

20

Explanation

We perform the following sequence of operations:

1. Add a contact named hack.
2. Add a contact named hackerrank.
3. Find and print the number of contact names beginning with hac. There are currently two contact names in the application and both of them start with hac, so we print on a new line.
4. Find and print the number of contact names beginning with hak. There are currently two contact names in the application but neither of them start with hak, so we print on a new line.

Source : https://www.hackerrank.com/challenges/ctci-contacts

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	import java.util.HashMap;
	public class Solution {
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();
	Trie trie = new Trie();
	for (int i = 0; i < n; i++) {
	String operation = scan.next();
	String contact = scan.next();
	if (operation.equals("add")) {
	trie.add(contact);
	} else if (operation.equals("find")) {
	System.out.println(trie.find(contact));
	}
	}
	scan.close();
	}
	}
	/* Based loosely on tutorial video in this problem */
	class TrieNode {
	private HashMap<Character, TrieNode> children = new HashMap();
	public int size = 0; // this was the main trick to decrease runtime to pass tests.
	public void putChildIfAbsent(char ch) {
	children.putIfAbsent(ch, new TrieNode());
	}
	public TrieNode getChild(char ch) {
	return children.get(ch);
	}
	}
	class Trie {
	TrieNode root = new TrieNode();
	public void add(String str) {
	TrieNode curr = root;
	for (char ch : str.toCharArray()) {
	curr.putChildIfAbsent(ch);
	curr = curr.getChild(ch);
	curr.size++;
	}
	}
	public int find(String prefix) {
	TrieNode curr = root;
	for (char ch : prefix.toCharArray()) {
	curr = curr.getChild(ch);
	if (curr == null) {
	return 0;
	}
	}
	return curr.size;
	}
	}
	// Discuss on HackerRank: https://www.hackerrank.com/challenges/ctci-contacts/forum/comments/246767