leetcode 49题 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例1
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
思路
方法一： 排序
方法二：计数
代码
/**
* @param {string[]} strs
* @return {string[][]}
*/
// var groupAnagrams = function(strs) {
// const map = new Map();
// for (const str of strs) {
// // 排序
// const arr = str.split("");
// arr.sort();
// const key = arr.toString();
// const list = map.get(key) ? map.get(key) : new Array();
// list.push(str);
// map.set(key, list);
// }
// return Array.from(map.values());
// };
const groupAnagrams = (strs) => {
// 计数
const map = new Map();
for (const str of strs) {
const array = new Array(26).fill(0);
const base = 'a'.charCodeAt();
// 计数每个字母出现出现的次数
for (const s of str) {
const num = s.charCodeAt();
const diff = num - base;
if (array[diff] === 0) {
array[diff] = 1;
} else {
array[diff]++;
}
}
// 计算当前map的key(通过遍历字母出现次数数组去组合)，并统计key对应的数组
// let key = "";
// for (let i=0; i<array.length; i++) {
// if (array[i] !== 0) {
// // key = 字母+次数
// key += String.fromCharCode(base + i);
// key += array[i];
// }
// }
const key = array.reduce((prev, curr, i) => {
if (curr !== 0) {
prev += String.fromCharCode(base + i);
prev += array[i];
}
return prev;
}, '');
const list = map.get(key) ? map.get(key) : new Array();
list.push(str);
// key 是唯一，所以能保证不重复
map.set(key, list);
}
return Array.from(map.values());
};
复杂度分析:
方法一：
- 时间复杂度: O(N)
- 空间复杂度：O(N)
方法二：
- 时间复杂度: O(N^2)
- 空间复杂度：O(N)