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.
  1. No Prefix Set
  2. Discussions

No Prefix Set

  • willy756_taiwan
     + 0 comments

    Use Trie with python and create find_prefix function. In find_prefix function, consider the inserting order. For example : words_1 = ["dogfood","dog"] or words_2= ["dog","dogfood"]. In word_1, the length of "dogfood" is longer than "dog", so that the current.is_word_end is not working. Thus, we have the return True outside the loop check. In word_2, the length of "dog" is shorter than "dogfood", When we check "dogfood", we will find "dog". Then we get the current.is_word_end is True.

    Besides, if there is not any same char in child node then we return False.

    from collections import defaultdict
class Node:
    def __init__(self):
        self.childs = defaultdict(Node)
        self.is_word_end = False

class Trie:
    def __init__(self):
        self.root = Node()
    
    def insert(self, word):
        current = self.root
        for char in word:
            current = current.childs[char]
        current.is_word_end = True
        
    def find_prefix(self, word):
        current = self.root
        for char in word:
            if char in current.childs.keys():
                current = current.childs[char]
                if current.is_word_end:
                    return True
            else:
                return False
        return True

def noPrefix(words):
    tries = Trie()
    for s in words:
        if tries.find_prefix(s):
            print("BAD SET")
            print(s)
            break
        else:
            tries.insert(s)
    else:
        print("GOOD SET")