# 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 = {}
current_node = root.setdefault(s[0],[0,{}])
if len(s) == 1:
current_node[0] += 1
else:

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()
if is_prefix(root,word):
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('\0');

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 {

PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

Trie trie = new Trie();

while (n-- > 0) {
break;
}
}

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;

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);
if(m) break;
}
else printf("GOOD SET\n");
return 0;
}```

## Problem solution in JavaScript programming.

```function TrieNode(letter){

this.letter = letter;
this.size = 0;
this.complete = false;
this.children = {};

}

TrieNode.prototype = {

//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 = {

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 = current.children[letter];*/

current.size++;

if(!current.hasChild(letter)){

if(current.complete) return {valid: false, error: name};

}

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) {
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];

if(!status.valid){

console.log([

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);
});```