CrackingTheCodeInterview-10.2(b).cpp

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>

#define MAX_A 10

using namespace std;

string sortedWord(string& anagram) {
	char* arr = new char[anagram.size() + 1];
	strcpy(arr, anagram.c_str());
	sort(arr,arr + anagram.size());

	return string(arr);
}

void groupAnagrams(string a[], int size) {
	// TODO: input validation

	map<string,vector<string>> hashMap;

	for (int i=0 ; i < size ; i++) {
		string key = sortedWord(a[i]);
		vector<string>& v = hashMap[key];
		v.push_back(a[i]);
	}

	int index = 0;
	for (map<string,vector<string>>::iterator it = hashMap.begin() ; it != hashMap.end() ; ++it) {
		vector<string>& v = it->second;
		for (int j=0 ; j < v.size() ; j++) {
			a[index] = v[j];
			index++;
		}
	}
}

void printA(string a[]) {
	cout << "[";
	for (int i=0 ; i < MAX_A ; i++) {
		if (i)
			cout << ",";
		cout << a[i];
	}

	cout << "]" << endl;
}

void test(string a[], int size) {
	groupAnagrams(a, size);
	printA(a);
}

int main() {
	string a[MAX_A] = {"abc","ab" ,"bca", "ba" ,"bac" , "aac", "caa", "zzz", "eee", "123" };
	test(a,MAX_A);
}