49. 字母异位词分组 #

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

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

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

解答：

直接对字符串排序 #

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res=new ArrayList<>();
        HashMap<String,List<String>> map=new HashMap<>();
        for(String str:strs){
            char[] arr=str.toCharArray();
            Arrays.sort(arr);
            String sortStr=new String(arr);
            if(map.containsKey(sortStr)){
                List<String> list=map.get(sortStr);
                list.add(str);
            }else{
                List<String> list=new ArrayList<>();
                list.add(str);
                map.put(sortStr,list);
            }
        }
        return new ArrayList<>(map.values());
    }
}

关键：

char[] arr=str.toCharArray();
Arrays.sort(arr);
String sortStr=new String(arr);

时间复杂度：

复杂度分析

时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklogk)。
空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

用字母频次作为Key #

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res=new ArrayList<>();
        HashMap<String,List<String>> map=new HashMap<>();
        for(String str:strs){
            char[] arr=str.toCharArray();
            int[] count=new int[26];
            for(char ch:arr){
                count[ch-'a']++;
            }
            StringBuilder sb=new StringBuilder();  
            for(int i=0;i<26;i++){
                if(count[i]!=0){
                    sb.append((char)(i+'a'));
                    sb.append(count[i]);
                }
            }
            String sortStr=sb.toString();
            if(map.containsKey(sortStr)){
                List<String> list=map.get(sortStr);
                list.add(str);
            }else{
                List<String> list=new ArrayList<>();
                list.add(str);
                map.put(sortStr,list);
            }
        }
        return new ArrayList<>(map.values());
    }
}

复杂度分析

时间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度，Σ 是字符集，在本题中字符集为所有小写字母，∣Σ∣=26。需要遍历 n 个字符串，对于每个字符串，需要 O(k) 的时间计算每个字母出现的次数，O(∣Σ∣) 的时间生成哈希表的键，以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(n(k+∣Σ∣))。
空间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的最大长度，Σ 是字符集，在本题中字符集为所有小写字母，∣Σ∣=26。需要用哈希表存储全部字符串，而记录每个字符串中每个字母出现次数的数组需要的空间为 O(∣Σ∣)，在渐进意义下小于 O(n(k+∣Σ∣))，可以忽略不计。

也可以直接使用一个大的字符数组作为键，这样的话，每一个字母的次数也是唯一确定的

// 创建一个字符数组，用于统计每个字符的出现次数
char[] cntMap = new char[26];
for (char ch : str.toCharArray()) {
    cntMap[ch - 'a']++;
}

// 将字符数组转换为字符串作为键
String key = new String(cntMap);

// 如果键不存在，则创建一个新的列表
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}