Skip to main content

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例 1:

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

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

解释：

在 strs 中没有字符串可以通过重新排列来形成 "bat"。 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。 示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

简单做法：两层遍历 时间复杂度 O (n²k)，其中 n 是字符串数量，k 是字符串的最大长度

进阶做法：可以通过对每个字符串进行排序，将排序后的字符串作为哈希表的键，将原字符串添加到对应键的值列表中。这样字母异位词会被映射到同一个键下，最终返回哈希表的值列表即可。

时间复杂度：O (n * k log k)，其中 n 是字符串数量，k 是字符串的最大长度。

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

代码解释：

  1. 排序生成键：将字符串转换为字符数组，排序后再拼接成字符串作为哈希表的键。
  2. 分组存储：遍历每个字符串，将其添加到对应排序键的数组中。
  3. 时间复杂度：O(n * k log k)，其中n是字符串数量，k是字符串的最大长度。
  4. 空间复杂度：O(n * k)，主要用于存储哈希表。