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<>();
res.add(t);
map.put(key, res.size()  1);
}
t.add(s);
}
return res;
}
Java beat 100%!!! use prime number


@chiranjeeb2 the sieve of Eratosthenes? For small n it's the easiest to do. But if we just need n primes, no matter what they are, and n is less then 40, we can go with Euler formula :) n^2 + n + 41. It gives primes from 41 to 1601.

@abi93k The solution is based on Fundamental theorem of arithmetic. The limitation would be a long string will cause overflow.

@ISherry Prime is a good one, but would easily overflow when multiplied. When it does, you would have collision, yet, there is no collision handling. So we can always constuct a testcase to make your solution fail.


@kotomi_null would you mind explaining Fundamental theorem of arithmetic. I think it's theorem about prime multiply, but I am not sure.


said in Java beat 100%!!! use prime number:
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<>(); res.add(t); map.put(key, res.size()  1); } t.add(s); } return res;
The idea is clear: we need to generate a unique key for each group of Strings. A product of several primes can only have one combination of factors, which makes the product a unique key for the Strings consisted with these certain chars.

Overflow is fatal, although the idea is brilliant.
Already discussed here,
https://discuss.leetcode.com/topic/12509/omnalgorithmusinghashwithoutsort