Sunday, 11 June 2017

Contacts problem from Hacker rank. Count the number of contacts with given prefix | TRIE data structure | Java Based Solution

Hello Friends,

I am today with you with yet another good programming challenge. I have taken this problem from Hackerrank. The link for the problem is : https://www.hackerrank.com/challenges/contacts

It asks us to build an algorithm similar to the contacts application we have in our mobile phones.
The operations we need to support are

  1. add (String contact) : The problem statement guarantees that always the contact will be unique
  2. count (String partial) : Return all the number of contacts with prefix as partial. 

Friends for solving the problem optimally we will use TRIE data structure. Please find below my code for the same.

package hacker.rank.trie.contacts;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        Node head = new Node();
        for(int i = 0; i < n ; i++){
            String lines = sc.nextLine();
            String[] commands = lines.split(" ");
            if(commands[0].equals("add")){
                head.add(commands[1]);
            }else{
                int answer = head.getCount(commands[1]);
                System.out.println(answer);
            }
        }
    }
    static class Node{
        Map<Character, Node> map = new HashMap<>();
        boolean isComplete = true;
        int count = 0;
        public void add(String contact){
            add(contact,0);
        }
        private void add(String contact, int index){
            count++;
            if(index == contact.length()){
                isComplete = true;
                return;
            }
            Node child = map.get(contact.charAt(index));
            if(child == null){
                child = new Node();
                map.put(contact.charAt(index),child);
            }
            child.add(contact,index+1);
        }
        
        public int getCount(String partial){
            return getCount(partial,0);
        }
        
        private int getCount(String partial, int index){
            if(index == partial.length()){
                return count;
            }
            Node child = map.get(partial.charAt(index));
            if(child == null){
                return 0;
            }
            return child.getCount(partial, index+1);
        }
    }   
}