49. 字母异位词分组 Medium

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

示例 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"]]

解题思路

输入：以个字符串数组 strs

输出：将字符串中使用了相同字母的组合在一起返回新的数组

本题属于 哈希表 问题。

我们可以遍历字符串数组的同时将每个字符串按字母大小排序作为一个 key

这样使用了相同的字母的字符串都会产生一个相同的 key

将相同 key 的字符串存在哈希表中，最后再导出新的数组

代码实现

python

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 使用 defaultdict(list) 存储分组结果
        # key: 排序后的字符串（作为“字母特征”）
        # value: 属于该特征的所有单词
        anagram_map = defaultdict(list)
        
        # 遍历每一个单词
        for word in strs:
            # 将单词的字母排序，作为“分组的唯一标识”
            # 例如 "eat" -> "aet", "tea" -> "aet"
            sorted_word = ''.join(sorted(word))
            
            # 把原始单词放入对应的分组中
            anagram_map[sorted_word].append(word)
        
        # 返回所有分组结果（只需要 values 即可）
        return list(anagram_map.values())

javascript

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map();

    for (let s of strs) {
        const key = s.split('').sort().join('');
        if (!map.has(key)) map.set(key, []);

        map.get(key).push(s);
    }

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

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

49 国际版

49 中文版