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

  • 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');
}