No Prefix Set

  • + 0 comments
    class TriNode:
        def __init__(self):
            self.childs={}
            self.end_word=False
    
    class Trie:
        def __init__(self):
            self.root = TriNode()
        def add(self, s):
            cur = self.root
            for ch in s:
                if ch in cur.childs:
                    cur = cur.childs[ch]
                    if cur.end_word:
                        return True #cases like ab, abc, when checks b in abc
                else:
                    new_node = TriNode()
                    cur.childs[ch] = new_node
                    cur = new_node
            cur.end_word=True
            return cur.childs  #cases like abc, ab, when checking ab
    
    
    def noPrefix(words):
        t = Trie()
        for w in words:
            p = t.add(w)
            if p:
                print(f"BAD SET\n{w}")
                return
        print("GOOD SET")