LeetCode Hot100 -2

49. 字母异位词分组 – 力扣（LeetCode）

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

排序做法：

通过排序，确定唯一有序的字符集合，记录在hash中。复杂度O(nmlog(m))。

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);

            map.computeIfAbsent(sortedStr, k -> new ArrayList<>());
            map.get(sortedStr).add(str);
        }
        return new ArrayList<>(map.values());
    }

计数做法：

通过枚举计数，算出每个字符串对应的字符数量，算出有序唯一值。复杂度O(nm)。

但是由于字符串转字符数组，字符数组转字符串有额外开销，耗时并不理想。

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] chr = new int[26];
            for (char c : str.toCharArray()) {
                chr[c - 'a']++;
            }

            String key = Arrays.toString(chr);
            map.computeIfAbsent(key, k -> new ArrayList<>());
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }

进阶做法：

利用算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。复杂度O(nm)。

注：虽然时间复杂度相同，但是没有字符串之间相互转换，耗时大大减少。

        static int[] prime = {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, 107};
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Integer, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int code = hash(str);

            if (!map.containsKey(code)) {
                map.put(code, new ArrayList<>());
            }
            map.get(code).add(str);
        }
        return new ArrayList<>(map.values());
    }

    static int hash(String str){
        int code = 1;
        for (char c : str.toCharArray()) {
            code *= prime[c - 'a'];
        }
        return code;
    }