leetcode 49. 字母异位词分组（Java版）

题目描述（题目难度，中等）

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目求解

利用算术基本定理高效求解。
算术基本定理：任何一个大于 1 的自然数，都可以写成一系列素数的乘积，且这个素数序列（这里以及下面提到的序列都是指不考虑元素顺序的序列）是唯一的。例如 12，只能分解为为 2，2，3 这三个素数的乘积，不可能存在其它素数序列的积为 12。
根据这个定理，我们把 26 个小写字母一一映射到 26 个不同的素数上，那么每个字符串都可以看作是一个素数序列。由乘法的可交换性知，无论这个字符串的字母如何交换位置，其对应的素数序列的乘积都是不变的。最重要的是，两个由不同字母序列组成的字符串对应的乘积值一定是不同的，绝对没有发生冲突的可能性。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
                       47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
        HashMap<Long, List<String>> map = new HashMap<Long, List<String>>();
        for (int i = 0; i < strs.length; ++i) {
            long key = 1;
            for(int j = 0; j < strs[i].length(); ++j){
                key *= prime[strs[i].charAt(j)-'a'];
            }
            List<String> list = map.get(key);
            if (list == null) {
                list = new ArrayList();
                map.put(key, list);
            }
            list.add(strs[i]);
        }
        return new ArrayList(map.values());
    }
}