【力扣热题100】哈希——字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 “bat”。
字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 “ate” ，“eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。

链接：[https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked)

思路

如果两个字符串，每个字母出现的次数是一样的，那么这两个字符串就是字母异位词。每个字符串中只有小写字母，那么可以有一个26位长度的数组arr表示，其中arr[i]的值代表字符串中，字符a+i出现的次数（eg：如果字符串中e出现了10次，那么arr[e-a]即arr[4]=10）。将每个字符串对应的数组转成String（不能直接数字转，需要位置对应的字母+数字），因此可以设置一个Map<String, List<String>>，其中key为字符串对应的数组转成String，value则是字符串列表。综上，是字母异位词的字符串对应的key相同的，因此把Map的Value转成List即可。

备注

字符串对应的数组转成String（不能直接数字转，需要位置对应的字母+数字）是因为比如[“bdddddddddd”,“bbbbbbbbbbc”]，第一个是1个b、10个d，第二个10个b，1个c。对应的数组分别为[0,1,0,10,0……]，[0,10,1,0,0,……]，直接转均为010100……。因此加上对应的字符，变为b1d10和b10c1

题解

class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            int[] counts = new int[26];
            for (char c : strs[i].toCharArray()) {
                counts[c - 'a']++;
            }
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < 26; j++) {
                if (counts[j] != 0) {
                    sb.append((char) ('a' + j));
                    sb.append(counts[j]);
                }
            }
            List<String> index = map.getOrDefault(sb.toString(), new ArrayList<>());
            index.add(strs[i]);
            map.put(sb.toString(), index);
        }
        return new ArrayList<List<String>>(map.values());
    }
}