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

|

232 Discussions

|

  • hacker_n6e15uxz
     + 0 comments

    C++17 code for your reference:

    void noPrefix(vector<string> words) {
    unordered_set<string_view> prefix_set, word_set;
    
    // iterate over all words, using references is crucial for unordered_set<string_view> to work
    for (const auto& w : words) {
        auto word_sv = string_view(w);
        
        // check if current word w is a prefix of any previous word
        if (prefix_set.count(word_sv)) {
            printf("BAD SET\n%s\n", w.c_str());
            return;
        }
        
        // iterate over all possible non-empty prefixes of current word w
        for (auto size=1u; size<=w.size(); size++) {
            auto word_prefix_sv = word_sv.substr(0, size);
            
            // check if any previous word is a prefix of current word w
            if (word_set.count(word_prefix_sv)) {
                printf("BAD SET\n%s\n", w.c_str());
                return;
            }
            
            // update prefix set
            prefix_set.insert(word_prefix_sv);
        }
        
        // update word_set
        word_set.insert(word_sv);
    }
    
    printf("GOOD SET\n");
}

  • ivanbilych
     + 0 comments

    C++11 variant with Trie. As it was pointed out tests want you to implement exactly this solution.

    class TrieNode {
    public:
        unordered_map<char, shared_ptr<TrieNode>> children;
        bool isEndOfWord;
        
        TrieNode() : isEndOfWord(false) {}
};

class Trie {
    public:
        Trie() : root(new TrieNode()) {}
        
        bool insert(string& word) {
            auto node = root;
            
            for (auto ch : word) {
                if (!node->children.count(ch)) {
                    node->children[ch] = shared_ptr<TrieNode>(new TrieNode());
                }
                
                node = node->children[ch];
                
                // Exit condition #1: This node is an end of some word
                if (node->isEndOfWord) {
                    return false;
                }
            }
            
            node->isEndOfWord = true;
            
            // Exit condition #2: This node is a prefix for some word
            if (!node->children.empty()) {
                return false;
            }
            
            return true;
        }
    
    private:
        shared_ptr<TrieNode> root;
};

void noPrefix(vector<string> words) {
    Trie trie;
    
    for (auto& word : words) {
        if (!trie.insert(word)) {
            cout << "BAD SET" << endl;
            cout << word << endl;
            return;
        }
    }
    
    cout << "GOOD SET" << endl;
}

  • alex_blinov
     + 0 comments

    Yes, agree, annoing test for this solution. The solution should not depend on tests. The most straitforward is to sort array and compare string i, and i+1. there is also more optimal solution even without sorting. Unfortunately test case rely on the specific non optimal brute force solution. This is not advance test if you ecourage others on this simplistic unefficicient solution to deal with (n*n)/2 string comparisons!

  • hideki_ryuga_pe1
     + 0 comments

    If you're wondering why your test case doesn't work, it's because the test cases are wrong, not your solution.

    They expect you to use a trie but this is not in the instructions, yet the order in which the first bad string appears depends entirely on your solution. The deteciton of any bad string should have been sufficient to solve this problem.

  • ds6890
     + 0 comments

    From reading this discussion it seems this is seeing if we used a trie. Even so, this doesn't timeout and I think the logic seems to check out. Given their criteria that words are tested in order, and the prefix 'aab' is lower indexed compared to 'aac'. Guess im skipping this one.

    def noPrefix(words):
    if len(words) == 1:
        return
    
    seen = set()

    for i in range(len(words)):
        target = words[i]
        seen.add(target)
        for j in range(i, len(words)):
            if i == j:
                continue

            if words[j] in seen:
                print("BAD SET")
                print(words[j])
                return
                
            if len(words[j]) > len(target) and words[j][0:len(target)] in seen:
                print("BAD SET")
                print(words[j])
                return