Algorithm


Problem Name: Data Structures - No Prefix Set

Problem Link: https://www.hackerrank.com/challenges/no-prefix-set/problem?isFullScreen=true

In this HackerRank in Data Structures - No Prefix Set solutions

There is a given list of strings where each string contains only lowercase letters from

, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string. In this case, print GOOD SET. Otherwise, print BAD SET on the first line followed by the string being checked.

Note If two strings are identical, they are prefixes of each other.

Example

words = ['abcd','bcd','abcde','bcde'

Here 'abcd' is a prefix of 'abcde' and 'bcd' is a prefix of 'bcde'. Since 'abcde' is tested first, print

BAD SET  
abcde

 

.

No string is a prefix of another so print

GOOD SET 

Function Description
Complete the noPrefix function in the editor below.

noPrefix has the following parameter(s):
- string words[n]: an array of strings

Prints
- string(s): either GOOD SET or BAD SET on one line followed by the word on the next line. No return value is expected.

Input Format
First line contains n, the size of words[].

Then next n lines each contain a string, words[i].

Constraints

1 <= n <= 10**5

1 <= the length of words[i] <= 60

All letters in words[i] are in the range 'a' through 'j', inclusive.

Sample Input00

STDIN       Function
-----       --------
7            words[] size n = 7
aab          words = ['aab', 'defgab', 'abcde', 'aabcde', 'bbbbbbbbbb', 'jabjjjad']
defgab  
abcde
aabcde
cedaaa
bbbbbbbbbb
jabjjjad

Sample Output00

BAD SET
aabcde

Explanation
'aab' is prefix of 'aabcde' so it is a BAD SET and fails at string 'aabcde'.

Sample Input01

4
aab
aac
aacghgh
aabghgh

Sample Output01

BAD SET
aacghgh

Explanation
'aab' is a prefix of 'aabghgh', and aac' is prefix of 'aacghgh'. The set is a BAD SET. 'aacghgh' is tested before 'aabghgh', so and it fails at 'aacghgh'.

 

 

Code Examples

#1 Code Example with C Programming

Code - 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;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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 > 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;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - 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();
		
	}	
	
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - 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);
}>;
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'noPrefix' function below.
#
# The function accepts STRING_ARRAY words as parameter.
#

def noPrefix(words):
    dic = {}
    for i in range(len(words)):
        start = dic
        for j in range(len(words[i])):
            if words[i][j] not in start:
                start[words[i][j]] = {}
            start = start[words[i][j]]
            if '*' in list(start.keys()) or (j == len(words[i]) - 1 and (start)):
                print("BAD SET\n", words[i], sep = '')
                return
        start['*'] = True
    print('GOOD SET')

if __name__ == '__main__':
    n = int(input().strip())

    words = []

    for _ in range(n):
        words_item = input()
        words.append(words_item)

    noPrefix(words)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Poisonous Plants solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Direct Connections solution in Hackerrank - Hacerrank solution C, C++, java,js, Python