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

  • charlieo
     + 0 comments

    Solution in Python, a little rusty on perfect Trie implementation but this did the trick.

    To tackle the ordering and avoid sorting the list, the key check is in

    if char in cur.children and (i == len(word) - 1 or cur.children[char].endOfWord):
`

    Full code:

    ``
class TrieNode:
    def __init__(self, val: Optional[str] = None):
        self.val = val
        self.endOfWord = False
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def add_new_word(self, word: str) -> bool:
        cur = self.root
        for i, char in enumerate(word):
            # next letter is already under root and marks end of word
            if char in cur.children and (i == len(word) - 1 or cur.children[char].endOfWord):
                return False
            next_node = cur.children.setdefault(char, TrieNode(char))
            cur = next_node

        if cur.endOfWord:
            return False

        cur.endOfWord = True
        return True 
    

def noPrefix(words) -> bool:
    trie = Trie()
    for word in words:
        if not trie.add_new_word(word):
            print("BAD SET")
            print(word)
            return False
    print("GOOD SET")
    return True


    noPrefix(words)