Problem:
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
Solution:
class Solution {
public:
vector<string> anagrams(vector<string> &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map<string, map<char, int> > strMap;
map<map<char, int>, int> mapCount;
vector<string> result;
if (strs.size() == 0)
return result;
for (int i=0; i < strs.size(); i++) {
map<char, int> charMap;
string str = strs[i];
for (int j = 0; j < str.size(); j++) {
charMap[str[j]] += 1;
}
strMap[str] = charMap;
mapCount[charMap] += 1;
}
for (int i = 0; i < strs.size(); i++) {
if (mapCount[strMap[strs[i]]] > 1) {
result.push_back(strs[i]);
}
}
return result;
}
};
============ Alternate =============
Instead of using:
map<char, int> charMap;
string str = strs[i];
for (int j = 0; j < str.size(); j++) {
charMap[str[j]] += 1;
}
we can sort each strs[i] and map this sorted string to its count, and use this mapping in the same way as we use mapCount above, like:
class Solution {
public:
vector<string> anagrams(vector<string> &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<string> solution;
int size = strs.size();
if (size < 2)
return solution;
map<string, int> count_map;
for (int i = 0; i < size; i++) {
string temp = strs[i];
sort(temp.begin(), temp.end());
count_map[temp]++;
}
for (int i = 0; i < size; i++) {
string temp = strs[i];
sort(temp.begin(), temp.end());
if (count_map[temp] > 1)
solution.push_back(strs[i]);
}
return solution;
}
};
==================== Alternate =====================
class Solution {
public:
vector<string> anagrams(vector<string> &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<string> solution;
map<string, vector<string> > hash;
int size = strs.size();
if (size < 2)
return solution;
for (int i = 0; i < size; i++) {
string sorted_str = strs[i];
sort(sorted_str.begin(), sorted_str.end());
if (!hash[sorted_str].empty())
hash[sorted_str].push_back(strs[i]);
else {
vector<string> hash_row;
hash_row.push_back(strs[i]);
hash[sorted_str] = hash_row;
}
}
map<string, vector<string> > :: iterator iter;
for (iter = hash.begin(); iter != hash.end(); iter++) {
vector<string> ans = iter->second;
int hash_row_size = ans.size();
if (hash_row_size == 1)
continue;
for (int j = 0; j < hash_row_size; j++) {
solution.push_back(ans[j]);
}
}
return solution;
}
};
==== Neat one ====
vector<vector<string>> groupAnagrams(vector<string>& strs) {
map<string, vector<string> > mp;
vector<vector<string> > ans;
for (int i = 0; i < strs.size(); i++) {
string tmp = strs[i];
sort(tmp.begin(), tmp.end());
mp[tmp].push_back(strs[i]);
}
map<string, vector<string> >::iterator it;
for (it = mp.begin(); it != mp.end(); it++) {
ans.push_back(it->second);
}
return ans;
}
{align = "center"}