LeetCode 0049.字母异位词分组

力扣题目链接：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 ≤ s t r s . l e n g t h ≤ 1 0 4 1leq strs.lengthleq 10^4 1≤strs.length≤104
• 0 ≤ s t r s [ i ] . l e n g t h ≤ 100 0leq strs[i].lengthleq100 0≤strs[i].length≤100
• s t r s [ i ] strs[i] strs[i] 仅包含小写字母

“字母异位词”是至每种字母出现次数都相同的单词。

例如“aba”和“aab”是“字母异位词”因为它们中“a”都出现了2次且“b”都出现了1次。

给你一些串，让你把这些串中同属于“字母异位词”的分为一组。

对于每个单词，我们只需要计算出其中每个字母出现的次数，然后用哈希表对应到一个分组中即可。

假如用C++实现，那么可以用map, vector>来充当哈希表。

对于每一个字符串，我们为其建立一个size为26的vector，以此来记录每个字母出现的次数。

还可以用vector来存放同组的字符串。

然后用这个计算出来的vector作为键值，映射到不同的每一组中去。

• 时间复杂度 O ( ∣ n ∣ ) O(|n|) O(∣n∣)，其中 ∣ n ∣ |n| ∣n∣是所有字符串的长度之和。
• 空间复杂度 O ( ∣ n ∣ ) O(|n|) O(∣n∣)

class Solution {
public:
    vector> groupAnagrams(vector& strs) {
        map, vector> ma;
        for (string& s : strs) {
            vector appendTime(26, 0);
            for (char& c : s) {
                appendTime[c - 'a']++;
            }
            ma[appendTime].push_back(s);
        }
        vector> ans;
        for (auto& [a, vs] : ma) {
            ans.push_back(vs);
        }
        return ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/124972260