Answer:
d, avt, car, feet, more, pitch, rome, tac, teef,
Anagrams of b in dictionary
Anagrams of cat in dictionary
avt, cat, tac,
Anagrams of room in dictionary
more, rome,
Anagrams of hello in dictionary
Anagrams of in dictionary
Explanation:
// FindAnagrams.cpp : it is the starting point of application console.
//
#include <vector>
#include <hash_map>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <set>
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("c");
dict.push_back("car");
dict.push_back("avt");
dict.push_back("taac");
dict.push_back("feet");
dict.push_back("teef");
dict.push_back("rom");
dict.push_back("more");
dict.push_back("pit");
dict.sort();
cout << "The dictionary: " << endl;
copy(dict.begin(), dict.end(), ostream_iterator<string>(cout, ", "));
cout << endl;
list<string> testCases;
testCases.push_back("d");
testCases.push_back("car");
testCases.push_back("rome");
testCases.push_back("hell");
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;
}
