Put together the words made of the same letters.
What to build
A map whose values are lists.
Requirements
- Read the words.
- Words whose sorted letters are the same belong to one group.
- Print one group per line, in order of the groups' sorted keys. Within a group, keep input order.
Input
The first line has n. The second line has n lowercase words.
Output
One line per group.
Constraints
n is from 1 to 200, and each word has at most 20 letters.
Example
Input:
5
listen silent enlist cat act
Output:
cat act
listen silent enlist
Why it works
Sorting turns "are these two related?" into a plain key lookup, and the map then does all of the grouping.
Examples
Example 1 · Input
5 listen silent enlist cat act
Expected output
cat act listen silent enlist
Example 2 · Input
1 abc
Expected output
abc
Hints
Hint 1
Sorting a word's letters gives the same key for all its anagrams.
Hint 2
A map from key to vector<string> keeps the groups.
Hint 3
Sort each word copy, not the word itself.
Solution
Show one correct solution (try it yourself first)
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
map<string, vector<string>> groups;
for (int i = 0; i < n; i++) {
string word;
cin >> word;
string key = word;
sort(key.begin(), key.end());
groups[key].push_back(word);
}
for (const auto& group : groups) {
const vector<string>& words = group.second;
for (size_t i = 0; i < words.size(); i++) {
cout << words[i] << (i + 1 < words.size() ? " " : "\n");
}
}
return 0;
}