No Prefix Set

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