LeetCode 49. 字母异位词分组：两种高效 C++ 解法

class Solution_Optimized {
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
        // 质数数组，映射 'a' 到 'z'。
        // **关键优化：避免使用质数 2。** (见下文分析)
        std::vector<int> primes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
        // 使用 unsigned long long 作为键，以容纳更大的乘积
        std::unordered_map<unsigned long long, std::vector<std::string>> m1;
        for(const std::string& s : strs) {
            unsigned long long key = 1;
            for(char ch : s) {
                // 1. 生成键：将字符映射到质数并相乘
                // ch - 'a' 得到 0-25 的索引
                key *= primes[ch - 'a'];
            }
            // 2. 归组
            m1[key].emplace_back(s);
        }
        // 3. 收集结果
        std::vector<std::vector<std::string>> ans;
        for(auto const& [key, group] : m1) {
            ans.emplace_back(group);
        }
        return ans;
    }
};

🔍 技巧与溢出陷阱分析

这种方法虽然高效，但涉及到一个关键的实现细节：哈希值溢出。

1. 利用 unsigned long long 的溢出特性

当多个质数相乘的结果超出 unsigned long long 的最大表示范围（2^64 - 1）时，会发生环绕溢出。

• 溢出后的结果： 结果会模 2^64。即 result = (P1 * P2 * ... * Pn) mod 2^64。
• 为何可行？ 尽管发生了溢出，由于乘法是可交换的（a × b = b × a），只要乘数集合（即字符集）相同，无论乘法顺序如何，最终得到的模 2^64 的结果依然是相同的。这保证了字母异位词的键值依然唯一。

2. 为何不能用质数 2？

这是这个方法中最巧妙且最容易出错的地方。

• 计算机的乘 2 操作： 在计算机底层，乘 2 操作等同于左移一位 (<< 1) 并在末尾补 0。
• 溢出后的问题： 当乘积不断累乘 2 并最终溢出unsigned long long 的范围时，结果在模 2^64 运算后，最高位会被丢弃。如果一个数不断乘以 2 导致其所有位都溢出，结果将变为 0。当连续乘以多个 2 后，结果可能会变成 0。一旦键值变为 0，后续任何字符对应的质数与 0 相乘，结果都将是 0。
• 结论： 键值一旦归 0，就无法区分是哪个字母异位词组导致了 0。为了保证不同字母异位词组不会意外得到相同的 0 键值，我们必须避免使用质数 2，从而规避这种特殊的乘法溢出陷阱。因此，我们将质数数组的起始值设为 3。

复杂度分析

• 时间复杂度： O(N * K)。
  • N 是输入字符串的数量。
  • K 是字符串的最大长度。
  • 生成键只需要遍历字符串，时间复杂度为 O(K)。
• 空间复杂度： O(N * K)。与解法一相同。

结论