-
Notifications
You must be signed in to change notification settings - Fork 120
/
GroupAnagrams.cpp
68 lines (49 loc) · 1.48 KB
/
GroupAnagrams.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*The two strings, X and Y, are anagrams if by rearranging X's letters,
we can get Y using all the original letters of X exactly once. For example, all these pairs are anagrams as lhs can be rearranged to rhs and vice-versa.*/
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;
set<set<string>> groupAnagrams(vector<string> const &words)
{
set<set<string>> anagrams;
// constructing a vector from the given words with each word sorted
vector<string> list(words);
for (string &s: list) { // don't forget to put `&`
sort(s.begin(), s.end());
}
unordered_map<string, vector<int>> map;
for (int i = 0; i < words.size(); i++) {
map[list[i]].push_back(i);
}
for (auto itr: map)
{
set<string> anagram;
for (int index: itr.second) {
anagram.insert(words[index]);
}
if (anagram.size() > 1) {
anagrams.insert(anagram);
}
}
return anagrams;
}
int main()
{
vector<string> words =
{
"CARS", "REPAID", "DUES", "NOSE", "SIGNED", "LANE", "PAIRED", "ARCS",
"GRAB", "USED", "ONES", "BRAG", "SUED", "LEAN", "SCAR", "DESIGN"
};
set<set<string>> anagrams = groupAnagrams(words);
for (set<string> anagram: anagrams) {
for (string s: anagram) {
cout << s << ' ';
}
cout << endl;
}
return 0;
}