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

|

173 Discussions

|

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

  • yonatanimm
     + 0 comments

    Java 8 solution, passed all the tests

        public static void noPrefix(List<String> words) {
        final Set<String> strings = new HashSet<>();
        final Set<String> subSets = new HashSet<>();
        final int size = words.size();
        for (int i=0; i< size; i++){
            final String checkedWord = words.get(i);
            //Check if the current word is subset of previous words
            if(subSets.contains(checkedWord)){
                System.out.println("BAD SET");
                System.out.print(checkedWord);
                return;
            }
            
            for(int j=1; j<=checkedWord.length(); j++){
                final String subSet = checkedWord.substring(0, j);
                //Check if any previous word is a subset of the current word
                if(strings.contains(subSet)){
                    System.out.println("BAD SET");
                    System.out.print(checkedWord);
                    return;
                }
                subSets.add(subSet);
            }
            strings.add(checkedWord);
        }
        
        System.out.println("GOOD SET");

    }

  • davitazizyan
     + 0 comments

    c++ solution

    bool isless_m( string str1,  string str2) {
    int N = min(str1.size(), str2.size());
    for (int i = 0; i < N; ++i) {
        if (str1[i] < str2[i]) {
            return true;
        }
        else if (str1[i] > str2[i]) {
            return false;
        }
    }
    return false;
}

void noPrefix(vector<string> words) {
       
    if (words.size() == 1) {
        cout << "GOOD SET\n";
        return;
    }    

    set<string,decltype(&isless_m)> mp(&isless_m);

    for (int i = 0; i < words.size(); ++i) {
        auto it=mp.insert(words[i]);
        if (!it.second) {
             cout << "BAD SET\n";            
            cout << words[i]<<"\n";
            return;
        }
    }
    cout << "GOOD SET\n";
   
}