Java beat 100%!!! use prime number

• ``````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;
}``````

• It's a good idea to solve the problem with prime numbers, but I can't get your solution for "For the return value, each inner list's elements must follow the lexicographic order." Could you explain the point?

• it can not ensure the lexicographic order.

• Can you explain the solution ?

• Genius solution....

• Nice solution but curious is there an efficient way to generate n number of prime numbers if I dont want to hard code 26 prime
numbers

• @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.

• What if the key you compute overflows?

• This post is deleted!

• For the input { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" } the answer is wrong...

• What if strs[i] contains too many value? It may cause overflow.

• Genius, although it may cause stackoverflow when strs[i] is too long

• @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.

• @ljj19921026 I am curious why no one upvote this

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

• @xiaowu4 got it.

• 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;
``````

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.