Check my anagram code from a job interview in the past.
- by Michael Dorgan
Had the following as an interview question a while ago and choked so bad on basic syntax that I failed to advance (once the adrenalin kicks in, coding goes out the window.)
Given a list of string, return a list of sets of strings that are anagrams of the input set. i.e. "dog","god", "foo" should return {"dog","god"}. Afterward, I created the code on my own as a sanity check and it's been around now for a bit. I'd welcome input on it to see if I missed anything or if I could have done it much more efficiently. Take it as a chance to improve myself and learn other techniques:
void Anagram::doWork(list input, list &output)
{
typedef list 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);
}
}
