HackerRank No Prefix Set problem solution

In this HackerRank No Prefix Set problem, we have given a list of strings where each string contains only lowercase letters and we need to find if no string is a prefix of another string then print GOOD SET otherwise print BAD SET.

Problem solution in Python programming.

root = {}
def add_to(root,s):
    current_node = root.setdefault(s[0],[0,{}])
    if len(s) == 1:
        current_node[0] += 1
    else:
        add_to(current_node[1],s[1:])
        
def is_prefix(root,s):
    if len(s) == 1:
        if len(root[s[0]][1])>0 or root[s[0]][0] > 1:
            return True
        else:
            return False
    else:
        if root[s[0]][0] > 0:
            return True
        else:
            return is_prefix(root[s[0]][1],s[1:])
    
    
    
n = int(input())
count = 0 
for _ in range(n):
    word = input().strip()
    add_to(root,word)
    if is_prefix(root,word):
        print("BAD SET")
        print(word)
        break
    count += 1
if count == n:
    print("GOOD SET")

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Trie {

    private static final int ALPHABET_SIZE = 26;

	class Node {
	    
	    Node[] edges;
	    char key;
	    int wordCount = 0;
	    int prefixCount = 0;
	    
	    Node(char key) {
	        this.key = key;
	        this.edges = new Node[ALPHABET_SIZE];
	    }
	    
	    boolean has(char key) {
	        return get(key) != null;
	    }
	    
	    Node get(char key) {
    	    return edges[getKey(key)];
	    }
	    
	    void put(char key, Node node) {
	        this.edges[getKey(key)] = node;
	    }
	    
	    char getKey(char ch) {
	        return (char) (ch - 'a');
	    }
	    
	}
		
	private Node root = new Node('');
	
	public boolean insert(String word) {
	    return insert(word, root);
	}
	
	private boolean insert(String word, Node root) {
    	root.prefixCount++;
        if (word.length() >= 0 && root.wordCount > 0) {
            return false;
        }
	    if (word.length() == 0) {
	        if (root.prefixCount > 1) {
	            return false;
	        }
	    	root.wordCount++;	    	
	    	return true;
	    }	    
	    char ch = word.charAt(0);
	    Node next = root.get(ch);	    
	    if (next == null) {
	        next = new Node(ch);	        
	        root.put(ch, next);
	    }	    
	    return insert(word.substring(1), next);	    
	}	
	
	public static void main(String[] args) throws IOException {		
	
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));		
		
		Trie trie = new Trie();        
        int n = Integer.parseInt(in.readLine());
        
        boolean bad = false;
        while (n-- > 0) {
            String word = in.readLine();  
            bad = !trie.insert(word);            
            if (bad) {
                out.println("BAD SETn"+word);    
                break;
            }
        }
        

        if (!bad) {
            out.println("GOOD SET");
        }        
        out.close();
		
	}	
	
}

Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <memory>
#include <unordered_map>

using namespace std;

class Trie
{
    public:
        bool insert(const string& s)
        {
            bool prefixFound = false;
            Node* node = &root;
            for (char c : s)
            {
                auto found = node->children.find(c);
                if (found == node->children.end())
                {
                    if (node->isWord) {
                        prefixFound = true;
                    }
                    Node* newNode = new Node();

                    node->children[c] = unique_ptr<Node>(newNode);
                    node = newNode;
                }
                else
                {
                    node = found->second.get();
                }
            }
            if (node->isWord) {
                prefixFound = true;
            }
            node->isWord = true;
            return prefixFound || node->children.size() > 0;
        }

    private:
        struct Node
        {
            bool isWord = false;
            unordered_map<char, unique_ptr<Node> > children;
        };

        Node root;
};



int main() {
    int n;
    cin >> n;
    
    Trie trie;
    string s;
    while (n--) {
        cin >> s;
        if (trie.insert(s)) {
            cout << "BAD SET" << endl;
            cout << s << endl;
            return 0;
        }
    }
    cout << "GOOD SET" << endl;
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct trieNode{
    struct trieNode **dic;
    int lw;
}tNode;

tNode *root;

int addStr(char *s){
    tNode *t;
    char c;
    t=root;
    while(*s){
        c = *s - 'a';
        s++;
        if(t->dic == NULL) t->dic=(tNode**)calloc(10,sizeof(tNode));
        if(t->dic[c] && t->dic[c]->lw) return 1;
        if((*s==0)&&(t->dic[c]!=NULL)) return 1;
        if(t->dic[c]==NULL) t->dic[c]=(tNode*)calloc(1,sizeof(tNode*));
        if(*s==0) t->dic[c]->lw=1;
        else t=t->dic[c];
    }
    return 0;
}

int main() {
    int n,m=0;
    char str[61];
    root=(tNode*)calloc(1,sizeof(tNode));
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s",str);
        m=addStr(str);
        if(m) break;
    }
    if(m) printf("BAD SETn%sn",str);
    else printf("GOOD SETn");
    return 0;
}

Problem solution in JavaScript programming.

function TrieNode(letter){
    
    this.letter = letter;
    this.size = 0;
    this.complete = false;
    this.children = {};
    
}

TrieNode.prototype = {
    
    addChild: function(letter){
        
         //if(!this.hasChild(letter))
         this.children[letter] = new TrieNode(letter);
        
    },
    
    hasChild: function(letter){
        
        return !!this.children[letter];
        
    }
    
};

function Trie(){
    
    this.root = new TrieNode('');
    
}

Trie.prototype = {
    
    add: function(name){
        
        let letters = name.split('');
        let current = this.root;
        
        for(let i = 0; i < name.length; i++){
            
            let letter = name.charAt(i);
            /*
            if(!current.hasChild(letter) && current.complete){
                
                return {valid: false, error: name};
                
            } 
            
            current.addChild(letter);      
            current = current.children[letter];*/
            
            current.size++;
            
            if(!current.hasChild(letter)){
                
                if(current.complete) return {valid: false, error: name};
             
                current.addChild(letter);
                
            }
            
            current = current.children[letter];
            
        }
        
        current.complete = true;
        if(current.size > 0) return {valid: false, error: name};
        
        current.size++;
        
        return {valid: true, error: ''};
        
    }
    
};

function processData(input) {
    //Enter your code here
    let lines = input.split('n');
    let n = lines[0];
    
    let trie = new Trie();
    
    for(let i = 0; i < n; i++){
        
        let entry = lines[1 + i];
        
        let status = trie.add(entry)
        if(!status.valid){
         
            console.log([
                
                'BAD SET',
                status.error
                
            ].join('n'));
            
            return;
            
        }
        
    }
    
    console.log('GOOD SET');
    
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});