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

Sort by

recency

|

209 Discussions

|

  • devms0201
     + 0 comments

    Do I have to predict HackRank's solution testing order?

  • 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")

  • 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)

  • zhangjunge9918
     + 0 comments

    I managed to have a solution passing tests other than dictionary tree. Sort the words. For each word check with words greater than it and break when not a prefix. Among the pair, the one with greater index in the unsorted original array is the one triggering the "BAD SET". However we need to iterate to the end and keep the first.

  • patrickhuynh97
     + 0 comments

    This problem is annoying because it is solution dependent and doing the most basic solution using sets/dicts is too slow to pass all the test cases. Any implementation of a Trie data structure will pass all tests though. Here is mine after some help cleaning up from our AI overlords:

    class TrieNode:
    def __init__(self):
        self.seen: dict[str, TrieNode] = {}
        self.word_end = False
    
    # Adds a node beneath the current node and returns it
    def add_node(self, character: str) -> Self:
        new_node = TrieNode()
        self.seen[character] = new_node
        return new_node
    
    # Returns a node if it exists beneath this node, otherwise None
    def get_node(self, character: str) -> Self | None:
        return self.seen.get(character)
        

class Trie:
    def __init__(self):
        self.nodes: dict[str, TrieNode] = {}
    
    def add_string(self, string: str):
        # Get the root node of this string
        c_1 = string[0]
        parent = self.nodes.get(string[0])
        
        # If it doesn't exist, create it
        if not parent:
            parent = TrieNode()
            self.nodes[c_1] = parent
            
        # Start at the parent, loop through the rest of the characters
        for i in range(1, len(string)):
            c_i = string[i]
            child_node = parent.get_node(c_i)
            
            # If a child node exists with this character, traverse to it
            if child_node:
                parent = child_node
            # Otherwise, we need to create it
            else:
                parent = parent.add_node(c_i)
        # Once we reach the end of the word, mark the final parent as the end of a word
        parent.word_end = True
                
    def search_string(self, string: str) -> bool:
        # Get the root node of this string
        root = self.nodes.get(string[0])
        
        # If there is no root node matching this string, return no match
        if not root:
            return False

        # If the string is only 1 character long or our root is a complete word
        if root.word_end or len(string) == 1:
            return True
        
        # Start at the root, loop through the rest of the characters
        parent = root
        for i in range(1, len(string)):
            # Get the next node in the tree
            parent = parent.get_node(string[i])
            
            # If there is no next node, then no prefix match exists
            if not parent:
                return False
                
            # If there is a next node and:
            #   1. If parent is a complete word, it is a prefix of our string
            #   3. If we have reached the end of our string, then it itself is a prefix of a seen word
            if parent.word_end or i == len(string) - 1:
                return True
            

def noPrefix(words):
    tree = Trie()
    for word in words:
        found = tree.search_string(word)
        if found:
            print("BAD SET")
            print(word)
            return
        else:
            tree.add_string(word)
    print("GOOD SET")