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('\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 {
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 SET\n"+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 SET\n%s\n",str);
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 = {
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);
});
0 Comments