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.
This is a very poorly worded problem in my opinion, and the given test cases are unclear / incomplete.
There are two things that you need to check for as you iterate through the list of original input words:
Is the current input word a prefix of any of the previously checked words? If yes, print "BAD SET" and print the current word (which is a prefix, this is what I think is very unclear from the description)
Is a prefix of the current word one of the words I've previously processed? If yes, print "BAD SET" and print the current word (not the prefix).
To check these two conditions I used a std::multiset to keep track of the input words (to be able to detect duplicate words), and a std::set to keep track of all previous prefixes to check input words against (I don't care about duplicates here, so a normal set will work just fine).
See my solution in C++14:
void noPrefix(vector<string> words) {
multiset<string> words_to_check; // set of words to add to as we process the original list, this must be a multiset so we can detect duplicate words
set<string> all_prefixes; // set of all prefixes of words we've already checked, this allows us to see if a new word in the list is a prefix to a word we've already checked
// cycle through all the words
for(auto w : words)
{
// check if current word is a prefix of other words
if(all_prefixes.find(w) != all_prefixes.end())
{
// we found the prefix in the original word set
cout << "BAD SET" << endl;
cout << w << endl;
return;
}
// check all 'prefixes' of current word in words_to_check set
string prefix = w;
while (!prefix.empty()) {
// insert each prefix in list of prefixes to check future words against
all_prefixes.insert(prefix);
// check to see if the current prefix matches a word we've seen before
if(words_to_check.find(prefix) != words_to_check.end();
{
// we found the prefix in the original word set
cout << "BAD SET" << endl;
cout << w << endl;
return;
} else {
// remove one character from back of prefix, creating a new prefix
prefix.pop_back();
}
}
// append the most recently checked word to my list of full words to check on future prefixes
words_to_check.insert(w);
}
// if we've checked every word in the original list and not found any prefixes, we must have a good set
cout << "GOOD SET" << endl;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
No Prefix Set
You are viewing a single comment's thread. Return to all comments →
This is a very poorly worded problem in my opinion, and the given test cases are unclear / incomplete.
There are two things that you need to check for as you iterate through the list of original input words:
Is the current input word a prefix of any of the previously checked words? If yes, print "BAD SET" and print the current word (which is a prefix, this is what I think is very unclear from the description)
Is a prefix of the current word one of the words I've previously processed? If yes, print "BAD SET" and print the current word (not the prefix).
To check these two conditions I used a std::multiset to keep track of the input words (to be able to detect duplicate words), and a std::set to keep track of all previous prefixes to check input words against (I don't care about duplicates here, so a normal set will work just fine).
See my solution in C++14: