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

示例 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
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        unordered_map<string, vector<string>> flag;
        for (int i = 0; i < strs.size(); i++) {
            string s = strs[i];
            sort(s.begin(), s.end());
            flag[s].push_back(strs[i]);
        }
        vector<vector<string>> ans;
        for (auto &m : flag)
            ans.push_back(m.second);
        return ans;
    }
};

第二种方法是根据字母出现的频率，构造一个新的字符串，使得字母异位词得到的新字符串相同

如2#3#12#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        unordered_map<string, vector<string>> flag;
        vector<int> counts(27, 0);
        for (string s : strs) {
            for (char c : s)
                counts[c - 'a']++;
            string key;
            for (int i = 0; i < 26; i++) {
                key += to_string(counts[i]) + '#';
                counts[i] = 0;
            }
            flag[key].push_back(s);
        }

        vector<vector<string>> ans;
        for (auto &m : flag)
            ans.push_back(m.second);
        return ans;
    }
};

第三种方法是给每个小写字母分配一个质数，a:2，b:3，c:5，然后把每个字符串的质数值乘一起，就能保证字母异位词的哈希值相等，但是要注意有时值会特别大