No Prefix Set Discussions |

2 months ago+ 1 comment

my Python 3 attempt by incrementally inserting words into a trie (thanks to inspiration from many of you guys) (must be some other "cleaner" way to do the create dict if not exists step, but I prefer readability in my own terms XD):

edit: simplified and updated thanks to @dgzwiro !

def noPrefix(words):
    #Write your code here
    _end = "_end"
    trie = {}
    
    #return the current word where the check fails
    def bad(s):
        print("BAD SET")
        print(s)
    
    #incremental insertion of words
    for word in words:
        current = trie
        #for each word, insert and change current map/dict per letter
        for c in word:
            #FAIL: a processed word is the prefix of the current word
            if _end in current:
                bad(word)
                return
            #create map/dict if missing
            if c not in current:
                current[c] = {}
            current = current[c]
        
        #FAIL: current word map/dict is not empty
        #meaning either:
        #- current word was already inserted in the trie
        #- current word was a prefix of previously inserted words
        if len(current) > 0:
            bad(word)
            return
        
        #mark the current node where the current word ends here
        current[_end] = _end
    print("GOOD SET")

Cookie support is required to access HackerRank