# Group Anagrams

10.2 Group Anagrams: Write a method to sort an array of strings so that all the anagrams are next to each other.

• O(NlogN) time?, O(N) extra space

• One way of doing this is first sort the strings, and pair them into a map.

• Then we can sort the map by its second value, then return its first value.

``````typedef std::pair<std::string, string> p;
struct Comp {
bool operator()(const p &left, const p &right) const {
return left.first < right.second;
}
};

void group_anagrams(vector<string> &strings) {
map<string, string> word_anagram;

for (int i = 0; i < strings.size(); i++) {
string cpy = strings.at(i);
sort(strings.at(i).begin(), strings.at(i).end());
word_anagram.insert( { { cpy }, { strings.at(i) } });
}

// dump into vector in order to make it sortable
vector<pair<string, string>> cpy(word_anagram.begin(), word_anagram.end());

sort(cpy.begin(), cpy.end(), Comp());

int count = 0;
for (auto &i : cpy) {
strings.at(count++) = i.first;
}

}

int main() {
vector<string> words = {"could", "cloud", "dance", "caned", "own", "now", "clams", "calms", "wings", "swing", "a" };

group_anagrams(words);
print(words);
}``````

Last updated