LeetCode热题100-第2题

题目：49. 字母异位词分组 - 力扣（LeetCode）

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例1：

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

示例2：

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

示例3：

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

分析：本题目需要将每个单词分别拆开成单独的字母，其字母组合是唯一的，不存在歧义，因此可以用哈希表将字母组合存储为键，而单词为值进行存储，最后遍历已经存储完毕的哈希表即可

python运用字典实现如下：

class Solution(object):
    def groupAnagrams(self, strs):
        anagrams = defaultdict(list)  # 创建一个默认字典，用于存储字母异位词的列表
        for str in strs:
            count = [0] * 26  # 创建一个长度为26的数组，用于记录'a'到'z'的频率
            for char in str:
                count[ord(char) - ord('a')] += 1  # 计算每个字符的频率
            anagrams[tuple(count)].append(str)  # 将频率数组转换为元组，以便它可以作为字典的键
        return list(anagrams.values())  # 返回所有字母异位词列表的列表

C++运用map来存储，但字母的组合必须转换成字符串，如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 创建一个unordered_map，用于存储字母异位词的分组
        unordered_map<string,vector<string>>mp;
        // 遍历输入的字符串向量
        for(string s : strs)
        {
            // 生成当前字符串的字母频率编码
            string key = countStr(s);
            // 将当前字符串添加到对应字母频率编码的组中
            mp[key].push_back(s);
        }
        vector<vector<string>>res;
        for(auto pair : mp)
        {
            // 遍历unordered_map，将每个分组添加到结果向量中
            res.push_back(pair.second);
        }

        return res;
    }

    // 此函数用于生成字符串的字母频率编码
    string countStr(string s){
        string res = "";
        int count[26] = {0};// 创建一个计数数组，用于记录每个字母的出现次数
        // 遍历字符串，统计每个字母的出现次数
        for(int i=0;i<s.length();i++)
        {
            count[s[i]-'a']++;
        }
        // 将计数数组的每个元素转换为字符串，并添加到结果字符串中
        for(int i=0;i<26;i++)
        {
            res+=to_string(count[i])+"#";
        }
        return res;
    }
};