-
Notifications
You must be signed in to change notification settings - Fork 0
/
group_anagrams.cpp
182 lines (154 loc) · 5.65 KB
/
group_anagrams.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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <catch2/catch_test_macros.hpp>
#include <string>
#include <vector>
#include <set>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <unordered_map>
#include <algorithm>
using namespace std;
namespace LeetCode{
/*README START
# <<Group Anagrams>>
[Leetcode #49](https://leetcode.com/problems/anagrams/).
Use a hash map to group anagrams, but instead of using a sorted string as key (so the default string hash code function would return same hash code for all subjects of the same anagram, it will work but the run time will be penalized for the sorting of every key), the solution implments a customized hash code function which uses the first 26 prime numbers to represent the 26 lower case letters and calculates the hash code by mulitplying them, to reflect the fact that 1) we only care about different letters 2) ordering does not matter.
Beats 99.75% of C++ submissions.
![Screenshot](img/leetcode/Anagrams.PNG)
README END*/
/*
https://leetcode.com/problems/anagrams/
Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note:
- For the return value, each inner list's elements must follow the lexicographic order.
- All inputs will be in lower-case.
*/
class GroupAnagrams{
private:
inline static int char_val(const char& c) {
return c - 'a';
}
inline static size_t hash(const string & key) {
auto n = key.size();
if (n == 0) return (size_t) 0;
size_t code = 1;
//first 26 prime numbers
static int primes [] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101 };
for(char c:key){
code *= primes[char_val(c)];
}
return code;
}
public:
inline static bool eq(const string& x, const string& y) {
if (x.size() != y.size()) {
return false;
}
else {
return hash(x)==hash(y);
}
}
vector<vector<string>> groupAnagrams(vector<string>& strs) {
typedef vector<string> V;
auto _hash = [](const string & key) {
return hash(key);
};
auto _eq = [](const string& x, const string& y) {
return eq(x, y);
};
sort(strs.begin(), strs.end());
unordered_map < string, int, decltype(_hash), decltype(_eq)> index(1024,_hash,_eq);
vector<V> r;
V item;
for (const auto& s : strs) {
auto pos = index.find(s);
if (pos == index.end()) {
r.push_back(item);
r.back().push_back(s);
index.insert(make_pair(s, (int)r.size()-1));
}
else {
V& v = r[pos->second];
v.push_back(s);
}
}
//for (auto& i : r) {
// sort(i.begin(), i.end());
//}
return r;
}
};
TEST_CASE("Group anagrams: customized equal","[leetcode]") {
{
string s1 = "eat";
string s2 = "tea";
string s3 = "ate";
string s4 = "tan";
REQUIRE(GroupAnagrams::eq(s1,s2));
REQUIRE(GroupAnagrams::eq(s1, s3));
REQUIRE(GroupAnagrams::eq(s2, s3));
REQUIRE_FALSE(GroupAnagrams::eq(s1, s4));
}
{
string s1 = "duh";
string s2 = "ill";
REQUIRE_FALSE(GroupAnagrams::eq(s1, s2));
}
}
TEST_CASE("Group anagrams: test case 1","[leetcode]") {
vector<string> s = { "eat", "tea", "tan", "ate", "nat", "bat" };
GroupAnagrams t;
auto r = t.groupAnagrams(s);
set<vector<string>> expected = {
{ "ate", "eat", "tea" },
{ "nat","tan" },
{ "bat" }
};
set<vector<string>> result;
copy(r.begin(), r.end(), inserter(result, result.begin()));
REQUIRE(result == expected);
}
TEST_CASE("Group anagrams: duplicated words test case","[leetcode]") {
vector<string> s = {
"hos", "boo", "nay", "deb", "wow", "bop", "bob", "brr", "hey", "rye", "eve", "elf", "pup", "bum", "iva", "lyx",
"yap", "ugh", "hem", "rod", "aha", "nam", "gap", "yea", "doc", "pen", "job", "dis", "max", "oho", "jed", "lye",
"ram", "pup", "qua", "ugh", "mir", "nap", "deb", "hog", "let", "gym", "bye", "lon", "aft", "eel", "sol", "jab"
};
set<vector<string>> expected = {
{ "sol" },{ "wow" },{ "gap" },{ "hem" },{ "yap" },{ "bum" },{ "ugh","ugh" },{ "aha" },{ "jab" },{ "eve" },{ "bop" },
{ "lyx" },{ "jed" },{ "iva" },{ "rod" },{ "boo" },{ "brr" },{ "hog" },{ "nay" },{ "mir" },{ "deb","deb" },{ "aft" },
{ "dis" },{ "yea" },{ "hos" },{ "rye" },{ "hey" },{ "doc" },{ "bob" },{ "eel" },{ "pen" },{ "job" },{ "max" },{ "oho" },
{ "lye" },{ "ram" },{ "nap" },{ "elf" },{ "qua" },{ "pup","pup" },{ "let" },{ "gym" },{ "nam" },{ "bye" },{ "lon" }
};
GroupAnagrams t;
auto r = t.groupAnagrams(s);
set<vector<string>> result;
copy(r.begin(), r.end(), inserter(result, result.begin()));
REQUIRE(result == expected);
}
TEST_CASE("Group anagrams: all single words test case","[leetcode]") {
vector<string> s = {"cab", "tin", "pew", "duh", "may", "ill", "buy", "bar", "max", "doc"};
GroupAnagrams t;
auto r = t.groupAnagrams(s);
set<vector<string>> expected = {
{ "cab" },{ "tin" },{ "pew" },{ "duh" },{ "may" },{ "ill" },
{ "buy" },{ "bar" },{ "max" },{ "doc" }
};
set<vector<string>> result;
copy(r.begin(), r.end(), inserter(result, result.begin()));
REQUIRE(result == expected);
}
TEST_CASE("Group anagrams: empty input test case","[leetcode]") {
vector<string> s = { "" };
GroupAnagrams t;
auto r = t.groupAnagrams(s);
REQUIRE(r.size() == 1);
}
}