No Prefix Set

                            Solution in C :

In C ++ :





#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct node {
    char end;
    struct node * next[10];
} head;

int check_prefix(string str){
    struct node *nptr = &head; 
    int i;
    int index;
    int new_node = 0;

    for(i=0;i<str.size();i++){
        index = ((int)str[i])%'a';
        if(nptr->next[index]==0) {
            nptr->next[index] = new node;
            nptr = nptr->next[index];
            memset (nptr,0,sizeof(struct node));
            new_node = 1;
        }
        else {
            nptr = nptr->next[index];
        }
        if(nptr->end == 1) {cout <<"BAD SET"<<endl; return 1;}
    }
    if(new_node == 0) {cout <<"BAD SET"<<endl; return 1;}
    nptr->end = 1; 
    return 0;
}


int main() {
     
    string str;
    int n;
    int i;
    
    cin >>n;
    for (i=0;i<n;i++){
        cin >> str;
        if (check_prefix(str))  break;
    }
    if(i!=n) cout << str <<endl;
    else cout << "GOOD SET" <<endl;
    return 0;
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class Trie{
    
    char c;
    boolean isEndOfString;
    Trie []children;
}

public class Solution {

    Trie root;
    void input(){
        Scanner sin = new Scanner(System.in);
        int N = sin.nextInt();
        root = new Trie();
        root.children = new Trie[26];                        
        boolean flag = false;
        for(int i = 0; i < N; i++){
            String s = sin.next();
            if(!flag)
                flag = insert(s);
        }
        if(!flag){
           System.out.println("GOOD SET"); 
        }
    }
    
    Trie newNode(char c){
        Trie newNode = new Trie();
        newNode.c = c;
        newNode.isEndOfString = false;
        newNode.children = new Trie[26];
        return newNode;
    }
    boolean insert(String s){
        Trie ptr = root;
        boolean flag = false;
        int i = 0;
        int ctr = 0;
        for(; i < s.length(); i++){
            char c = s.charAt(i);
            int index = (int)c - 97;
            if(ptr.children[index] == null){
                Trie newNode = newNode(c);
                ptr.children[index] = newNode;                
                ptr = ptr.children[index];
            }
            else{
                ctr++;
                ptr = ptr.children[index];
                if(ptr.isEndOfString){
                    flag = true;
                    break;
                }
            }
        }
        if(i == s.length()){
            ptr.isEndOfString = true;    
        }
        if(flag){
            System.out.println("BAD SET");
            System.out.println(s);
        }
        else if(ctr == s.length()){
            System.out.println("BAD SET");
            System.out.println(s); 
            flag = true;
        }
        
        return flag;
    }
    
    public static void main(String[] args) {
        Solution s = new Solution();
        s.input();
    }
}








In C :




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


typedef struct node
{
    int is_word;
    struct node* children[10];
}*NODE;

NODE head=NULL;

NODE GetNewNode()
{
    NODE temp = (NODE)malloc(sizeof(struct node));
    temp->is_word = 0;
    int i;
    for(i=1;i<=5;i++)
        temp->children[i]=NULL;
    return temp;
}

void Insert(char word[])
{
    int digit;
    //printf("%d\n",rev);
    NODE temp;
    if(head==NULL)
    {
        head = GetNewNode();
    }
    temp=head;
    int i=0;
    while(word[i]!='\0')
    {
        digit = word[i];
        digit=digit-97;
        
        if(temp->children[digit]==NULL)
        {
            temp->children[digit]=GetNewNode();
        }
        temp = temp->children[digit];
        i++;
    }
    temp->is_word=1;
}

int Search(char word[])
{
    int digit,found=0;

    NODE temp = head;
    if(temp==NULL)return 0;
    int i=0;
    while(word[i]!='\0')
    {
        digit=word[i];
        digit=digit-97;
        if(temp->children[digit]==NULL)
            return 0;
        temp=temp->children[digit];
        if(temp->is_word==1)return 1;
        i++;
    }
    if(word[i]=='\0')//Check if we have scanned all characters....if we have, then prefix present       
        found=1;
   return found;
}



int main(void)
{
  char words[61];
  int number;
    int bad_set=0;
  scanf("%d",&number);
  while(number--)
  {
      scanf("%s",words);
      if(Search(words)==1)
      {
          printf("BAD SET\n%s",words);
          bad_set=1;
         break;
      }
      else
          Insert(words);
  }
    if(bad_set==0)
        printf("GOOD SET");
}







In Python3 :







class solution:
    def checkSET(self, strs):
        trie = dict()
        for cstr in strs:
            curr = trie
            for ch in cstr:
                if ch not in curr:
                    curr[ch] = dict()
                curr = curr[ch]
                if '_end' in curr:
                    return cstr
            if len(curr) > 0:
                return cstr
            curr['_end'] = ''
        return ''
    
n = int(input())
strs = []
for i in range(n):
    strs.append(input())
sol = solution()
ret = sol.checkSET(strs)
if ret == '':
    print('GOOD SET')
else:
    print('BAD SET')
    print(ret)