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

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

💡 解法一：排序作为哈希键 (经典方法)

核心思路

字母异位词的本质是字符和数量完全相同。因此，将任何一组字母异位词按字典序排序后，它们都会得到一个唯一的、规范化的字符串。我们利用这个规范化的字符串作为哈希表的键，将所有原始字符串归类到对应的值列表中。

C++ 代码实现

class Solution {
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
        // 哈希表：键是排序后的规范字符串，值是原始字符串列表
        std::unordered_map<std::string, std::vector<std::string>> m1;
        for (const std::string& s : strs) {
            std::string temp = s;
            // 1. 生成键：对字符串进行排序
            std::sort(temp.begin(), temp.end());
            // 2. 归组：将原始字符串添加到对应键的值列表中
            m1[temp].push_back(s);
        }
        // 3. 收集结果
        std::vector<std::vector<std::string>> ans;
        // 使用结构化绑定 (C++17) 遍历 map
        for (auto const& [key, group] : m1) {
            ans.emplace_back(group);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度： O(N·K log K)。
  • N 是输入字符串的数量。
  • K 是字符串的最大长度。
  • 主要开销在于对每个字符串进行排序（O(K log K)）。
• 空间复杂度： O(N·K)。用于存储哈希表和结果。

---

🔥 解法二：质数乘积作为哈希键 (优化方法)

核心思路

为了避免排序带来的 O(K log K) 时间开销，我们可以利用数学中的算术基本定理（唯一分解定理）。该定理指出：任何一个大于 1 的自然数都可以分解为有限个质数的乘积，并且这种分解是唯一的。

我们将 26 个小写字母 a 到 z 分别映射到一个唯一的质数。对于一个字符串，将其所有字符对应的质数相乘得到一个乘积。由于质数分解的唯一性，只有字母异位词才会得到相同的乘积。这个乘积作为哈希表的键，可以实现 O(K) 时间复杂度的键生成。

C++ 代码实现