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. Prepare
  2. Data Structures
  3. Trie
  4. No Prefix Set
  5. Discussions

No Prefix Set

Sort by

recency

|

175 Discussions

|

  • reubenfbeeler1
     + 0 comments
    from collections import defaultdict

def noPrefix(words):
    def dd():
        return [defaultdict(dd), 0]
    
    trie = dd()
    
    for word in words:
        cur = trie
        cur[1] += 1
        for c in word:
            if cur[1] > 1 + sum(count for (_, count) in cur[0].values()):
                # A word has ended here, so it is a prefix
                #  of the current word
                print('BAD SET')
                print(word)
                return
            cur = cur[0][c]
            cur[1] += 1
        if cur[1] > 1:
            # More than this word has reached here, so
            #  this word is a prefix
            print('BAD SET')
            print(word)
            return
    
    print('GOOD SET')

  • sudhansu3299
     + 0 comments

    Really really bad description! I was solving to get the string (whichever is larger) from the previous one in the list

  • linxiaotian
     + 0 comments

    Really bad problem description.

    "the string being checked." means you maintain a set which is empty at first. Then you need to check (or process, or add) the word one by one".

    And when you found 1. the current string is a prefix any string in the set, or 2. any string in the set is a preifx of current string

    You print current string.

  • tuan_lq121100
     + 0 comments

    Test case 1 answer is 'd' is actually correct one, because you insert 'd' after you insert 'dbajkhbhbjdh' (the previous string), and right at that time, the function should determine that the word array is a BAD SET, so it should print out BAD SET d. Below are my JS code which apply Trie structure.

    class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfString = false;
        this.count = 0;
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    insert(word) {
        let node = this.root;
        for(let char of word) {
            if(!node.children[char]) {
                node.children[char] = new TrieNode()
            }
            node = node.children[char];
            node.count += 1;
        }
        node.isEndOfString = true;
    }
    isGoodSet(word) {
        let node = this.root;
        for(let i=0; i< word.length; i++) {
            node = node.children[word[i]];
            if(node.isEndOfString === true && node.count > 1) return false;
        }
        return true;
    }
}
function noPrefix(words) {
    // Write your code here
    let trie = new Trie();
    for(let word of words) {
        trie.insert(word);
        if(!trie.isGoodSet(word)) {
            console.log('BAD SET');
            console.log(word);
            return;
        }
    }
    console.log('GOOD SET');
}

  • tsangwailam
     + 1 comment

    Why submission TestCase 1 is print "d" ? but not "dcjaichjejgheiaie"?

    "dcjaichjejgheiaie" should test before "d".