✅49. 字母异位词分组

[bazinga-web]

49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序。

[bazinga-web]

解题思路：

1. 如果为空数组直接返回空数组
2. 遍历单词数组，为每个单词建立长度为26的内容为0的数组，同时遍历每个单词将
   每个字母出现的频率记录到数组指定位置（利用ASCII码）
3. 将同等频率的单词放入Hash Map中
4. 遍历map，将结果返回

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  let result = [];
  if (strs.length === 0) return result;
  let map = new Map();
  for (const str of strs) {
    let arr = new Array(26).fill(0);
    for (let i = 0; i < str.length; i++) {
      const ascii = str[i].charCodeAt() - 97;
      arr[ascii]++;
    }
    const key = arr.join("");
    if (map.has(key)) {
      map.set(key, [...map.get(key), str]);
    } else {
      map.set(key, [str]);
    }
  }
  for (const value of map.values()) {
    result.push(value);
  }
  return result;
};

[Ray-56]

哈希表解

复杂度O(NKlogK), N 为 strs 长度，K 为 strs 中每个字符串的长度

const len = strs.length;
	if (!len) return [];
	const ret = [];
	const map = new Map();
	for (let i = 0; i < len; i++) {
		let newStr = strs[i].split('').sort().join(''); // 拆分排序合并后作为 key
		if (map.has(newStr)) {
			const old = map.get(newStr);
			old.push(strs[i]);
			map.set(newStr, old);
		} else {
			map.set(newStr, [strs[i]]);
		}
	}

	return Array.from(map.values());