49. 字母异位词分组

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

示例 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 &lt;= strs.length &lt;= 10<sup>4</sup>​
• ​0 <= strs[i].length <= 100​
• ​strs[i] 仅包含小写字母

struct PairHash {
    size_t operator()(const pair<uint64_t,uint64_t>& p) const noexcept {
        return p.first ^ (p.second << 1);
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        static const uint64_t S1[26] = {
            1572869ULL, 3145739ULL, 6291469ULL, 12582917ULL, 25165843ULL, 50331653ULL,
            100663319ULL, 201326611ULL, 402653189ULL, 805306457ULL, 1610612741ULL, 3221225473ULL,
            4294967311ULL, 8589934663ULL, 17179869209ULL, 34359738421ULL, 68719476767ULL,
            137438953447ULL, 274877906899ULL, 549755813881ULL, 1099511627753ULL, 2199023255531ULL,
            4398046511093ULL, 8796093022151ULL, 17592186044399ULL, 35184372088777ULL
        };
        static const uint64_t S2[26] = {
            2031617ULL, 4063237ULL, 8126477ULL, 16252933ULL, 32505863ULL, 65011741ULL,
            130023497ULL, 260046981ULL, 520093949ULL, 1040187821ULL, 2080375699ULL, 4160751381ULL,
            8321502781ULL, 16643005533ULL, 33286011061ULL, 66572022049ULL, 133144044107ULL,
            266288088223ULL, 532576176451ULL, 1065152352917ULL, 2130304705873ULL, 4260609411753ULL,
            8521218823553ULL, 17042437647101ULL, 34084875294203ULL, 68169750588427ULL
        };

        unordered_map<pair<uint64_t,uint64_t>, vector<string>, PairHash> mp;
        mp.max_load_factor(0.5f);
        mp.reserve(strs.size() * 2);

        for (auto& s : strs) {
            uint64_t h1 = 0, h2 = 0;
            for (char c : s) {
                int idx = c - 'a';
                h1 += S1[idx];
                h2 += S2[idx];
            }
            mp[{h1, h2}].push_back(s);
        }

        vector<vector<string>> ans;
        ans.reserve(mp.size());
        for (auto& kv : mp) {
            ans.push_back(std::move(kv.second));
        }
        return ans;
    }
};