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

提示:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写英文字母

解题思路

这道题的核心思想是找到一种方法来唯一标识字母异位词，使得所有字母异位词都有相同的标识符。

方法一：排序作为键（推荐）

最直观的方法是将每个字符串排序后作为哈希表的键。字母异位词排序后会得到相同的字符串，因此可以用排序后的字符串作为分组依据。

具体步骤：

  1. 遍历输入数组中的每个字符串
  2. 对当前字符串进行排序，得到排序后的字符串作为键
  3. 将原字符串添加到哈希表中对应键的列表中
  4. 最后将哈希表中所有的值（字符串列表）收集到结果数组中

方法二：字符计数作为键

另一种方法是统计每个字符串中各字符的出现次数，用计数数组或字符串来表示。由于题目限定只包含小写英文字母，可以用长度为26的数组来计数，然后将计数结果转换为字符串作为键。

两种方法的时间复杂度都是合理的，但排序方法更简洁易懂，是推荐解法。

代码实现

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
        
        for (string& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            groups[key].push_back(s);
        }
        
        vector<vector<string>> result;
        for (auto& pair : groups) {
            result.push_back(pair.second);
        }
        
        return result;
    }
};

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        
        for s in strs:
            key = ''.join(sorted(s))
            if key not in groups:
                groups[key] = []
            groups[key].append(s)
        
        return list(groups.values())

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var groups = new Dictionary<string, List<string>>();
        
        foreach (string s in strs) {
            char[] chars = s.ToCharArray();
            Array.Sort(chars);
            string key = new string(chars);
            
            if (!groups.ContainsKey(key)) {
                groups[key] = new List<string>();
            }
            groups[key].Add(s);
        }
        
        var result = new List<IList<string>>();
        foreach (var group in groups.Values) {
            result.Add(group);
        }
        
        return result;
    }
}

var groupAnagrams = function(strs) {
    const groups = new Map();
    
    for (let s of strs) {
        const key = s.split('').sort().join('');
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key).push(s);
    }
    
    return Array.from(groups.values());
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
排序作为键O(n × k × log k)O(n × k)
字符计数作为键O(n × k)O(n × k)

其中 n 是字符串数组的长度，k 是字符串的平均长度。

  • 排序方法：每个字符串需要 O(k log k) 的时间进行排序
  • 计数方法：每个字符串需要 O(k) 的时间进行字符计数
  • 空间复杂度：主要用于存储哈希表，最坏情况下所有字符串都不是字母异位词

相关题目