49 Group 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: All inputs will be in lower-case.
- Algorithm:
- Map each sorted word (key) to its actual word (vector of values).
- Thats it
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for (auto str : strs) {
string word = str;
sort(str.begin(), str.end());
//auto &found = map.find(str);
if (map.find(str) == map.end()) {
map.insert({ { str },{ word } });
}
else {
map.find(str)->second.push_back(word);
}
}
vector<vector<string>> anagrams;
for (auto i : map) {
anagrams.push_back(i.second);
}
return anagrams;
}
int main() {
vector<string> strs = {
"eat", "tea", "tan", "ate", "nat", "bat"
};
print2d(groupAnagrams(strs));
}
Last modified 4yr ago