Некоторое время назад я задавал себе следующий вопрос на собеседовании и так сильно задохнулся от базового синтаксиса, что мне не удалось продвинуться вперед (как только адреналин начинает действовать, кодирование исчезает).
Учитывая список строк, верните список наборов строк, которые являются анаграммами входного набора. т.е. "собака", "бог", "фу" должны вернуть {"собака", "бог"}. Впоследствии я создал код самостоятельно для проверки работоспособности, и он уже некоторое время существует. Я хотел бы получить информацию об этом, чтобы увидеть, пропустил ли я что-нибудь или мог бы сделать это гораздо более эффективно. Воспользуйтесь возможностью улучшить себя и изучить другие техники:
void Anagram::doWork(list input, list> &output)
{
typedef list < pair < string, string>> SortType;
SortType sortedInput;
// sort each string and pair it with the original
for(list< string >::iterator i = input.begin(); i != input.end(); ++i)
{
string tempString(*i);
std::sort(tempString.begin(), tempString.end());
sortedInput.push_back(make_pair(*i, tempString));
}
// Now step through the new sorted list
for(SortType::iterator i = sortedInput.begin(); i != sortedInput.end();)
{
set< string > newSet;
// Assume (hope) we have a match and pre-add the first.
newSet.insert(i->first);
// Set the secondary iterator one past the outside to prevent
// matching the original
SortType::iterator j = i;
++j;
while(j != sortedInput.end())
{
if(i->second == j->second)
{
// If the string matches, add it to the set and remove it
// so that future searches need not worry about it
newSet.insert(j->first);
j = sortedInput.erase(j);
}
else
{
// else, next element
++j;
}
}
// If size is bigger than our original push, we have a match
// - save it to the output
if(newSet.size() > 1)
{
output.push_back(newSet);
}
// erase this element and update the iterator
i = sortedInput.erase(i);
}
}
Вот второй шаг после просмотра комментариев и получения дополнительной информации:
void doBetterWork(list input, list> &output)
{
typedef std::multimap< string, string > SortedInputType;
SortedInputType sortedInput;
vector< string > sortedNames;
for(vector< string >::iterator i = input.begin(); i != input.end(); ++i)
{
string tempString(*i);
std::sort(tempString.begin(), tempString.end());
sortedInput.insert(make_pair(tempString, *i));
sortedNames.push_back(tempString);
}
for(list< string >::iterator i = sortedNames.begin(); i != sortedNames.end(); ++i)
{
pair< SortedInputType::iterator,SortedInputType::iterator > bounds;
bounds = sortedInput.equal_range(*i);
set< string > newSet;
for(SortedInputType::iterator j = bounds.first; j != bounds.second; ++j)
{
newSet.insert(j->second);
}
if(newSet.size() > 1)
{
output.push_back(newSet);
}
sortedInput.erase(bounds.first, bounds.second);
}
}
