# Group-Anagrams

Oct 15, 2017

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.

unsigned hashString(string &s) {
int sum = 1;
int count[26]{0};
for(auto c:s)
count[c-'a']++;
for(int i = 0;i < 26;i++){
sum = sum*133 + count[i];
}
return sum;
}


vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string> > ret;
unordered_map<unsigned,int> mRet;
int now = 0;
for(auto &s:strs) {
unsigned h = hashString(s);
cout << h << endl;
if (mRet.find(h) == mRet.end()){
ret.push_back({});
mRet[h] = now;
now++;
}
ret[mRet[h]].push_back(s);
}
return ret;
}


dicuss中有另外一种hash的方法:

public static List<List<String>> groupAnagrams(String[] strs) {
int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};//最多10609个z
List<List<String>> res = new ArrayList<>();
HashMap<Integer, Integer> map = new HashMap<>();
for (String s : strs) {
int key = 1;
for (char c : s.toCharArray()) {
key *= prime[c - 'a'];
}
List<String> t;
if (map.containsKey(key)) {
t = res.get(map.get(key));
} else {
t = new ArrayList<>();
map.put(key, res.size() - 1);
}
}
return res;
}


vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string> > anagrams;
for (string s: strs) {
string sorted = s;
sort(sorted.begin(), sorted.end());
anagrams[sorted].push_back(s);
}
vector<vector<string> > res;
for (auto p: anagrams) res.push_back(p.second);
return res;
}


public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map<String, List> ans = new HashMap<String, List>();
int[] count = new int[26];
for (String s : strs) {
Arrays.fill(count, 0);
for (char c : s.toCharArray()) count[c - 'a']++;

StringBuilder sb = new StringBuilder("");
for (int i = 0; i < 26; i++) {
sb.append('#');
sb.append(count[i]);
}
String key = sb.toString();
if (!ans.containsKey(key)) ans.put(key, new ArrayList());