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. Prepare
  2. Data Structures
  3. Trie
  4. No Prefix Set
  5. Discussions

No Prefix Set

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 152 Discussions, By:

recency

Please Login in order to post a comment

  • oscar_gohan2010
    3 weeks ago+ 0 comments

    Hi, I would like to know what's the expected output for this example:

    2

    ab

    a

    thanks!

    1|
    Permalink
  • imbisigeoffrey
    4 months ago+ 1 comment

    C++ Solution. Passed all the tests

    class Trie{
    
        public:
        Trie *childNodes[10];
        int wordCount;
    
        Trie(){
        for(int i=0;i<10;i++){
    
            childNodes[i]=NULL;
        }
        wordCount = 0;
        }
    
    };
    
    bool insert_key(Trie *root, string key_word){
    
    Trie *currentNode = root;
    
    for(int i=0;i<key_word.size();i++){
        int index = key_word[i]-'a';
    
        if(currentNode->childNodes[index]==NULL){
            Trie *newNode = new Trie();
            currentNode->childNodes[index]= newNode;
        }
        else{
            if(currentNode->childNodes[index]->wordCount || i==key_word.size()-1){
    
                return false;
           }
        }
        currentNode = currentNode->childNodes[index];
    }
      currentNode->wordCount++;
      return true;
    }
    
    void noPrefix(vector<string> words) {
      Trie *root = new Trie();
    for(auto word : words){
      if(!insert_key(root, word)){
          cout<< "BAD SET \n"<< word;
          return;
      }
    }
    cout<<"GOOD SET ";
    
    }
    
    0|
    Permalink
  • ottdavid23
    4 months ago+ 0 comments

    Completed by creating a tree representation of the word set.

    class Tree:
        def __init__(self, words):
            self.words = words
            self.root = Node(None)
            self.checkForPrefix()
            
            
        def checkForPrefix(self):
            for word in words:
                answer = self.insert(word)
    
                if answer is not None:
                    print("BAD SET")
                    print(answer)
                    return
        
            print("GOOD SET")
            
    
        def insert(self, word):
            current = self.root
            
            for i in range(len(word)):
                c = word[i]
                
                if current.branches[self.indexOf(c)] != None and i == len(word) - 1:
                    return word
                
                if current.branches[self.indexOf(c)] == None:
                    current.branches[self.indexOf(c)] = Node(c)
                
                if current.branches[self.indexOf(c)].isComplete:
                    return word
                
                if i == len(word) - 1:
                    current.branches[self.indexOf(c)].isComplete = True
                    
                current = current.branches[self.indexOf(c)]
    
            return None
    
        def indexOf(self, c):
            return ord(c) - 97
            
         
    class Node:
        def __init__(self, value):
            self.value = value
            self.isComplete = False
            self.branches = [None] * (ord("j") - ord("a") + 1)    
        
    
    
    def noPrefix(words):
        # Write your code here
        root = Tree(words)
    
    0|
    Permalink
  • mzimmer52
    5 months ago+ 0 comments

    No need to make this more complicated than it should be

    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')
    
    0|
    Permalink
  • alexdanapur
    8 months ago+ 0 comments

    Regular expression is best to match pattern. If you want validation like checking the value / length of matched expression / subexpression, it is better to do that outside regex. Keep your regex as simple as possible, so you don’t waste computational time for something that can be done more efficiently outside regex. https://wordmaker.info/how-many/prefix.html

    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