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

|

216 Discussions

|

  • yesmanmx
     + 0 comments

    Kotlin Building Trie and checking on a fly

    fun noPrefix(words: Array<String>): Unit {
    // Write your code here
    val tree = Node("")
    for (word in words) {
        var key = tree.text
        var parentNode = tree
        for (char in word) {
            key += char
            val node = parentNode.children.find { it.text == key } ?: Node(key)
                .also(parentNode.children::add)
            if (node.isWord) {
                println("BAD SET")
                println(word)
                return
            }
            parentNode = node
        }
        if (parentNode.children.isNotEmpty()) {
            println("BAD SET")
            println(word)
            return
        }
        parentNode.isWord = true
    }
    println("GOOD SET")
}

data class Node(
    var text: String,
    var isWord: Boolean = false,
    var children: MutableCollection<Node> = mutableListOf(),
) {
}

  • qchien_t
     + 0 comments

    if you run the code that exceed the time limit, try to use the hashmap to store the data C# code 

    public static void noPrefix(List<string> words)
    {
        var hashSetData = new Dictionary<string,List<int>>();
        var num = words.Count;
        var prefixes = new List<string>();
        for(int i = 0 ; i< num ; i++) {
            var word = words[i];
            if(hashSetData.ContainsKey(word)) { hashSetData[word].Add(i);}
            else {
                var data = new List<int>();
                data.Add(i);
                hashSetData.Add(word , data );
            }
        }
        var nextIndexCheckData = num + 1;
        for(int i = 0 ; i < num ; i++) {
            var word = words[i];
            if(i == nextIndexCheckData) {
                Console.WriteLine("BAD SET\n" + word);
                return;
            }
            var length = word.Length;
            for(int j = length ; j >= 1 ; j--) {
                var subString = word.Substring(0 , j);
                if(hashSetData.ContainsKey(subString)) {
                    var data = hashSetData[subString];
                    foreach(var idx in data) {
                        if(idx < i) {
                            Console.WriteLine("BAD SET\n" + word);
                            return;
                        } else if (idx > i && idx < nextIndexCheckData) {
                            nextIndexCheckData = idx;
                        }
                    }
                }
            }
        }
        
        Console.WriteLine("GOOD SET");
    }

  • svella
     + 0 comments

    This is a bad exercise because the "correct" result depends on processing in a particular order which is not called out in the requirements.

  • engnr_plusplus
     + 0 comments

    There isn't a unique correcrt answer in many test cases. How to handle those?

  • erlandohbs
     + 0 comments

    be careful with the limit memory, can not do manual way, only with trie on python 

    class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            # If we reach a node that is the end of another word, it's a BAD SET
            if node.is_end_of_word:
                return False
        # Mark the end of this word
        node.is_end_of_word = True
        # If this word is a prefix of any existing word, it's a BAD SET
        if node.children:
            return False
        return True

def noPrefix(words):
    trie = Trie()
    for word in words:
        if not trie.insert(word):
            print("BAD SET")
            print(word)
            return
    print("GOOD SET")