[数据结构与算法]leetcode: 49. 字母异位词分组

49. 字母异位词分组

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/group-anagrams/

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

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

解法

• 排序+哈希表：对每一个字符串做排序后，作为哈希表的key，这样就能将包含相同元素的字符串归类到一起；
• 计数+哈希表：由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键；

代码实现

排序+哈希表

python实现

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        counts = dict()
        for s in strs:
            ss = ''.join(sorted(s))
            if ss in counts:
                counts[ss].append(s)
            else:
                counts[ss] = [s]
        return list(counts.values())

c++实现

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> counts;
        for(auto str: strs) {
            string ss = str;
            sort(ss.begin(), ss.end());
            auto it = counts.find(ss);
            if (it != counts.end())
                counts[ss].push_back(str);
            else
                counts[ss] = {str};
        }
        
        vector<vector<string>> ans;
        for (auto it=counts.begin(); it != counts.end(); it++)  {
            ans.push_back(it->second);
        }

        return ans;    
    }
};

复杂度分析

• 时间复杂度： $O(KNlogK)$ N是strs中字符串的数量，K是strs中字符串最大长度
• 空间复杂度： $O(KN)$

计数+哈希表

python实现

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)

        for st in strs:
            counts = [0] * 26
            for ch in st:
                counts[ord(ch) - ord("a")] += 1
            # 需要将 list 转换成 tuple 才能进行哈希， list不能作为key
            mp[tuple(counts)].append(st)
        
        return list(mp.values())

c++实现

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n=strs.size();
        if(n==1) return vector<vector<string>>{{strs[0]}};
        vector<vector<string>> res;
        unordered_map<string,int> mp;
        int index=0;
        for(int i=0;i<n;i++){
            string str=strs[i];
            string count(26,0);
            for(int j=0;j<str.size();j++){
                count[str[j]-'a']++;
            }
            if(mp.find(count)!=mp.end())res[mp[count]].push_back(str);
            else {
                mp[count]=index;
                res.push_back(vector<string>{str});
                index++;
            }
        }
        return res;
    }
};

复杂度分析

• 时间复杂度： $O(N)$
• 空间复杂度： $O(N)$

注意

Python中字典的key都可以是什么？

答：python中字典的key不能是可变类型。字典可存储任意类型对象，其中值可以取任何数据类型，但键必须是不可变的，如字符串、数字或元组。
一个对象能不能作为字典的key，就取决于其有没有__hash__方法。所以所有python自带类型中，除了list、dict、set和内部至少带有上述三种类型之一的tuple之外，其余的对象都能当key。