Solution
// FindAnagrams.cpp : Defines the entry point for the console application.
//
#include <vector>
#include <hash_map>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <set>
Problem
Given a dictionary of English words, return the set of all words grouped into subsets of words that all anagrams of each other.
using namespace std;
using namespace stdext;
bool IsAnagrams(string& strA, string& strB)
{
list<char> listA(strA.begin(), strA.end());
list<char> listB(strB.begin(), strB.end());
listA.sort();
listB.sort();
return listA == listB;
// return equal(listA.begin(), listA.end(), listB.begin());
}
string SortChars(string str)
{
list<char> l(str.begin(), str.end());
l.sort();
return string(l.begin(), l.end());
}
set<string> FindAnagrams(list<string>& dict, string findStr)
{
map<string, set<string>> d;
typedef pair<string, set<string>> MyPair;
for(list<string>::const_iterator it = dict.begin(); it != dict.end(); ++it){
string str(SortChars(*it));
if(d.find(str) == d.end()){
set<string> s;
s.insert(*it);
d.insert(MyPair(str, s));
}
else{
d[str].insert(*it);
}
}
string sortedStr(SortChars(findStr));
return d[sortedStr];
}
int main(int argc, char* argv[])
{
list<string> dict;
dict.push_back("a");
dict.push_back("cat");
dict.push_back("act");
dict.push_back("tac");
dict.push_back("foot");
dict.push_back("toof");
dict.push_back("room");
dict.push_back("moor");
dict.push_back("pitch");
dict.sort();
cout << "The dictionary: " << endl;
copy(dict.begin(), dict.end(), ostream_iterator<string>(cout, ", "));
cout << endl;
list<string> testCases;
testCases.push_back("b");
testCases.push_back("cat");
testCases.push_back("room");
testCases.push_back("hello");
testCases.push_back("");
for(list<string>::iterator it = testCases.begin(); it != testCases.end(); ++it)
{
cout << endl << "Anagrams of " << *it << " in dictionary" << endl;
set<string> output = FindAnagrams(dict, *it);
copy(output.begin(), output.end(), ostream_iterator<string>(cout, ", "));
cout << endl;
}
return 0;
}
Output
The dictionary:
a, act, cat, foot, moor, pitch, room, tac, toof,
Anagrams of b in dictionary
Anagrams of cat in dictionary
act, cat, tac,
Anagrams of room in dictionary
moor, room,
Anagrams of hello in dictionary
Anagrams of in dictionary
Press any key to continue . . .