We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. No Prefix Set
  2. Discussions

No Prefix Set

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 146 Discussions, By:

recency

Please Login in order to post a comment

  • jun_ma4
    3 weeks ago+ 0 comments

    It can be solved with a custom trie.

    class Trie {
    public:
        bool insert(string word) {
            if (!head) {
                head.reset(make_node(L'\0'));
            }
            
            bool foundPrefix = true;
            auto working = head.get();
            for (auto c : word) {
                const auto idx = c - 'a';       
                if (working->isLeaf) {
                    // hit a prefix trying to insert the word
                    return true;
                }
                
                if (!working->children[idx]) {
                    // we are appending to the trie, so no prefix was found.
                    working->children[idx].reset(make_node(c));  
                    foundPrefix = false;
                }
                
                working = working->children[idx].get();
            }
            
            if (working) {
                working->isLeaf = true;
            }
            
            return foundPrefix;
        }
        
    private:
        struct Node {
            char data;
            std::unique_ptr<Node> children[10];
            bool isLeaf;
        };
        
        Node* make_node(char d) {
            return new Node{ d, {}, false };
        }
        
        std::unique_ptr<Node> head{};
    };
    
    void noPrefix(vector<string> words) {
        Trie t;
        for (auto word : words) {
            if (t.insert(word))
            {
                printf("BAD SET\n");
                printf("%s\n", word.c_str());
                return;
            }
        }
        
        printf("GOOD SET\n");
    }
    
    0|
    Permalink
  • Deepikadhanola
    1 month ago+ 0 comments

    I am here to let you know that this program is taking my soul out of my body mean for some input the expected output is too weird how can the first prefic they found is in posititon 12 or 16

    0|
    Permalink
  • juanmirocks
    1 month ago+ 0 comments

    Python3 solution gist


    As other users already pointed out, the problem description on what means "first checked" is confusing.

    The tests effectively "define" first checked as the first word, which is either a:

    • a) prefix of a previously seen word, or
    • b) prefixed by a previously seen word
    5|
    Permalink
  • akshay721
    2 months ago+ 0 comments

    My solution in Python 3 using trie

    # Node of a prefix tree
    class Node:
        def __init__(self):
            self.children = {}
            self.EndOfWord = False
    
    # Trie data structure
    class Trie:
        def __init__(self):
            '''
            Initialize a prefix tree with a root node.
            '''
            self.root = Node()
        
        def insert(self, word: str) -> bool:
            '''
            Insert a word into the prefix tree. Return True if any existing word is a prefix of currently inserted word. Else, return False.
            '''
            current = self.root
            flag = False
            for c in word:
                if c not in current.children:
                    current.children[c] = Node()
                current = current.children[c]
                if current.EndOfWord and not flag:
                    flag = True
            current.EndOfWord = True 
            return flag
        
        def startswith(self, prefix:str) -> bool:
            '''
            Does the prefix tree contain entries starting with a specific prefix?
            '''
            current = self.root
            for c in prefix:
                if c not in current.children:
                    return False
                current = current.children[c]
            return True
            
    def noPrefix(words: list[str]) -> None:
        '''
        Say N = len(words) and L = max word length.
        Space complexity: O(NL)
        Time complexity: O(NL)
        '''
        # Write your code here
        trie = Trie()
        for word in words:
            # Check if word exists in trie. If not, add word to trie.
            if trie.startswith(word):
                print('BAD SET', word, sep='\n')
                return None
            # When inserting word into trie, determine if any pre-added word in trie is a prefix of the newly added word.
            bool_flag = trie.insert(word)
            if bool_flag:
                print('BAD SET', word, sep='\n')
                return None
        print('GOOD SET') 
    
    0|
    Permalink
  • jaosn
    2 months ago+ 0 comments

    This is my c++ solution...not sure why people balk at rolling their own trie data struct in c++

    //simple trie data struct
    class PrefixTrie
    {
        public:
      
        unordered_map<char, PrefixTrie*> children;
    
    };
    
    void noPrefix(vector<string> words) {
        PrefixTrie root;
        
        //track if we are creating a new branch
        bool onNewBranch = true;
        
        for(string w : words)
        {
            PrefixTrie *next = &root;
            
            //add the word to the trie
            //if we encounter a node with no children then that means
            //we have seen the word before and its a prefix so bad set
            //also, if we add the entire word and never got to a new branch
            //then its a prefix of a word already in the tree
            for(char c : w)
            {         
                
                //if the node has children then its not a word we have seen   
                if(next->children.empty() && !onNewBranch)
                {
                    cout << "BAD SET\n" << w << "\n";
                    return;
                }
                //if the character doesnt exist in the children
                //then we are making a new branch
                if(next->children.find(c) == next->children.end())
                {
                    next->children[c] = new PrefixTrie();
                    onNewBranch = true;
                }
                
                next = next->children[c];
            }
            //if we got here but didnt make our own branch then we 
            //are part of another word'd branch and therefor a prefix
            if(!onNewBranch)
            {
                cout << "BAD SET\n" << w << "\n";
                return;  
            }
            
            onNewBranch = false;
        }
        
        cout << "GOOD SET\n";
    }
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy