Sunday, 11 June 2017

TRIE based java solution for Hacker rank : good set, bad set problem.

Hi Friends,

I am here with a problem, which is based on the No Prefix Set. It is about a set of input strings and we are supposed to find out if any string in the set is prefix of  any other one in the string. 

We are given N strings, we have to print "GOOD SET" if none of the strings in the set are prefix of any other string in the set. 
If any string is a prefix of any other string in the set then we are supposed to print "BAD SET" followed by the FIRST string for which such condition is detected in the set.

Link for the problem is : https://www.hackerrank.com/challenges/no-prefix-set

Please find below the TRIE based java solution for the same.

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 line = sc.nextLine();
            if(!head.add(line)){
                System.out.println("BAD SET");
                System.out.println(line);
                sc.close();
                return;
            }
        }
        System.out.println("GOOD SET");
    }
    static class Node{
        Map<Character, Node> map = new HashMap<>();
        boolean isComplete;
        public boolean add(String word){
            return add(word,0);
        }
        private boolean add(String word, int index){
            if(isComplete){
                return false;
            }
            if(index == word.length()){
                isComplete = true;
                return true;
            }
            Node child = map.get(word.charAt(index));
            if(child == null){
                child = new Node();
                map.put(word.charAt(index),child);
            }else if(index + 1 == word.length()){
                return false;
            }
            return child.add(word,index+1);
        }
    }   
}