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

出处：LeetCode

解法一：哈希表

思路

我们可以使用哈希表来存储每个单词的字母频次，然后将字母频次相同的单词放在一起。

代码

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const str of strs) {
    const count = new Array(26).fill(0);
    for (let i = 0; i < str.length; i++) {
      count[str.charCodeAt(i) - 97]++;
    }
    const key = count.join('#');
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key)!.push(str);
  }
  return Array.from(map.values());
}

上面的代码中：

• count 数组用来存储每个单词的字母频次，其中 count[i] 表示字母 i + 97 的频次。
• key 是将 count 数组转换为字符串后的结果，用来作为哈希表的键。
• 当 map 中不存在 key 时，我们将 key 作为键，对应的值初始化为空数组。
• 当 map 中存在 key 时，我们将当前单词添加到对应的值中。
• 最后返回 map 中的所有值。

复杂度分析

• 时间复杂度：$O(n \cdot m)$，其中 $n$ 是数组 strs 的长度，$m$ 是数组中字符串的平均长度。
• 空间复杂度：$O(n \cdot m)$。

解法二：排序

思路

我们可以将每个单词排序后作为哈希表的键，将字母异位词放在一起。

代码

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const str of strs) {
    const key = str.split('').sort().join('');
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key)!.push(str);
  }
  return Array.from(map.values());
}

上面的代码中：

• key 是将单词排序后的结果，用来作为哈希表的键。
• 当 map 中不存在 key 时，我们将 key 作为键，对应的值初始化为空数组。
• 当 map 中存在 key 时，我们将当前单词添加到对应的值中。
• 最后返回 map 中的所有值。

复杂度分析

• 时间复杂度：$O(n \cdot m \log m)$，其中 $n$ 是数组 strs 的长度，$m$ 是数组中字符串的平均长度。
• 空间复杂度：$O(n \cdot m)$。

解法三：质数相乘

思路

我们可以使用质数来表示每个字母，然后将每个单词的字母相乘得到一个唯一的值，将字母异位词放在一起。

代码

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<number, string[]>();
  const primes = [
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101
  ];
  for (const str of strs) {
    let key = 1;
    for (let i = 0; i < str.length; i++) {
      key *= primes[str.charCodeAt(i) - 97];
    }
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key)!.push(str);
  }
  return Array.from(map.values());
}

上面的代码中：

• primes 数组存储了前 26 个质数，用来表示每个字母。
• key 是将每个单词的字母相乘得到的结果，用来作为哈希表的键。
• 当 map 中不存在 key 时，我们将 key 作为键，对应的值初始化为空数组。
• 当 map 中存在 key 时，我们将当前单词添加到对应的值中。
• 最后返回 map 中的所有值。

复杂度分析

• 时间复杂度：$O(n \cdot m)$，其中 $n$ 是数组 strs 的长度，$m$ 是数组中字符串的平均长度。
• 空间复杂度：$O(n)$。