字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
codeType
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
codeType
输入: strs = [""]
输出: [[""]]
示例 3:
codeType
输入: strs = ["a"]
输出: [["a"]]
提示：
- 1 <= strs.length <= 104
- 0 <= strs[i].length <= 100
- strs[i] 仅包含小写字母
解法：
解法一：
逐个比较词频，词频用map统计。（时间复杂度 O(n * k * m)，n 是字符串数量，k 是字符串最大长度，m 是分组数量）。
ts
function groupAnagrams(strs: string[]): string[][] {
// 两个单词是否是字母异位词，可以通过hashmap统计词频后进行比较。
// 不需要每个单词之间都比较一遍，每个单词和每个类别比较一遍即可
const n = strs.length
const mapList: Map<string, number>[] = []
const res: string[][] = []
strs.forEach((str) => {
// 统计当前单词的词频
const curMap = new Map<string, number>()
for(let i = 0; i < str.length; i++){
if(curMap.has(str[i])){
curMap.set(str[i], curMap.get(str[i]) + 1)
}else{
curMap.set(str[i], 1)
}
}
// 比较词频
if(!mapList.some((map, index) => {
if(curMap.size !== map.size) return false // map大小不同
for(const [key, value] of map.entries()){
if(curMap.get(key) !== value) return false // 词频不同
}
res[index].push(str) // 找到字母异位词，push到对应列表
return true
})){
// 没找到字母异位词，自己新开一列
mapList.push(curMap)
res.push([str])
}
})
return res
};
解法二：
更优的方案是 通过「字符排序后的字符串」作为 key 进行分组（时间复杂度 O(n * k log k)，k 是字符串最大长度），代码更简洁高效：
ts
function groupAnagrams(strs: string[]): string[][] {
// 用 Map 存储：key=排序后的字符串，value=对应异位词数组
const groupMap = new Map<string, string[]>();
strs.forEach((str) => {
// 字符串排序：将异位词转为相同的key（如 "eat" 和 "tea" 排序后都是 "aet"）
const sortedStr = str.split('').sort().join('');
// 若key不存在，初始化空数组；若存在，直接获取原有数组
const curGroup = groupMap.get(sortedStr) || [];
curGroup.push(str);
groupMap.set(sortedStr, curGroup);
});
// 将 Map 的 value 转为数组返回
return Array.from(groupMap.values());
};