49. 字母异位词分组

题目

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
示例 2:

输入: strs = [“”]
输出: [[“”]]
示例 3:

输入: strs = [“a”]
输出: [[“a”]]

提示：

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

思路

回看之前做的思路是用26个质数表示每个字母，计算每个字符串的乘积，如果相等说明两个字符串互为“字母异位词”。在测试用例比较弱的时候的确可以过，今天再看新加的几个果然过不了了。当时还觉得自己的做法挺不错，现在看来有些搞笑…

更为方便严谨的做法是统计字符串每个字母的次数，使用统计出来的次数构造一个唯一不会冲突的字符串作为哈希表的，然后对应存储字母异位词。

比如对于字符串“”，可以构造为”“，这样不会存在相同而不是字母异位词的情况。

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] arr = s.toCharArray();
            int[] count = new int[26];
            for (char c : arr) {
                count[c - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            // 构造哈希表key
            for (int i = 0; i < 26; i++) {
                if (count[i] > 0) {
                    sb.append((char) ('a' + i)).append(count[i]);
                }
            }
            map.computeIfAbsent(sb.toString(), k -> new ArrayList<>()).add(s);
        }
        // map.values()可以直接传入ArrayList的构造函数中，不用使用for循环
        List<List<String>> ans = new ArrayList<>(map.values());
        return ans;
    }
}