leetcode_49.字母异位词分组

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] 仅包含小写字母

代码思路：

对于给定的字符串数组 strs 中的每个字符串 s：

1. 将字符串 s 转换为字符数组 cs。
2. 对字符数组 cs 进行排序，使得相同字母的字符串在排序后具有相同的字符顺序。
3. 将排序后的字符数组 cs 转换为字符串 key，作为分组的键。
4. 从哈希映射 temp 中获取键 key 对应的值，如果键不存在则创建一个新的空列表。
5. 将原始字符串 s 添加到对应分组的列表中。
6. 更新哈希映射 temp 中键 key 对应的值为更新后的列表。

使用了哈希映射来实现，只需要遍历一次字符串数组，将每个字符串排序后作为键存入哈希映射中，然后将属于同一组的字符串放入对应的值中，最后，将哈希映射中的所有值（即分组后的字符串列表）返回作为结果。

这个算法的时间复杂度为 O(n * mlogm)，其中 n 是字符串数组的长度，m 是字符串的平均长度。因为需要对每个字符串进行排序，排序的时间复杂度是 O(mlogm)。而算法的空间复杂度为 O(n * m)，主要是哈希映射和存储分组后的字符串列表所占用的空间。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> temp = new HashMap<>();
        for (String s : strs) {
            char[] cs = s.toCharArray();
            Arrays.sort(cs);
            String key = Arrays.toString(cs);
            List<String> value = temp.getOrDefault(key, new LinkedList<>());
            value.add(s);
            temp.put(key, value);
        }
        return new LinkedList<>(temp.values());
    }
}