一、题目描述
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明：
所有输入均为小写字母。 不考虑答案输出的顺序。
二、解题思路
两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同。同一组字母异位词中的字符串具备相同点，可以使用相同点作为一组字母异位词的标志，使用哈希表存储每一组字母异位词，哈希表的键为一组字母异位词的标志，哈希表的值为一组字母异位词列表。
遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26 的数组记录每个字母出现的次数。需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。
三、代码
代码语言：javascript复制public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Set set=new HashSet<>();
HashMap<Map,List<String>> map=new HashMap();
for(int i=0;i<strs.length;i ){
String str=strs[i];
Map<Character,Integer> wordCount=new HashMap<>();
for(int j=0;j<str.length();j ){
char c=str.charAt(j);
int cnt=wordCount.getOrDefault(c,0);
wordCount.put(c,cnt 1);
}
List<String> list= (List<String>) map.getOrDefault(wordCount,new ArrayList<String>());
list.add(str);
map.put(wordCount,list);
}
List<List<String>> rs=new ArrayList<>();
for(List<String> list:map.values()){
rs.add(list);
}
return rs;
}
}四、复杂度分析
时间复杂度：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 ∣Σ∣))，可以忽略不计。
