LeetCode 2 - 字母异位词分组 | 很多时候不懂事

📝 题目描述

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

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例：


示例 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]仅包含小写字母

💡 解题思路

方法一：排序解法

互为字母异位词的字符串中，包含的字母是相同的。根据此特性，我们可以对字符串内的字符按字母排序，结果相同的字符串必定互为字母异位词，故可以将排序之后的字符串作为哈希表的键。

方法二：计数解法

由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。

由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26 的数组记录每个字母出现的次数。需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。

这种方法的优点就是避开了排序的 $O(k \ logk)$ 开销，转而利用字母频率作为哈希表的键。

🔧 代码实现

1、排序解法

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 创建哈希表
        unordered_map<string, vector<string>> hash_map;
        // 遍历字符串数组
        for(string& str: strs){
            string s = str;
            // 排序字符串
            sort(s.begin(), s.end());
            // 插入哈希表
            hash_map[s].push_back(str);
        }
        vector<vector<string>> ans;
        // 遍历哈希表，存入每一个字母异位词数组
        for(auto it : hash_map){
            ans.emplace_back(it.second);
        }
        return ans;
    }
};

2、计数解法

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 定义一个 lambda 表达式 arrayHash
        // fn = hash<int>{} 获取标准库计算整数哈希的对象
        // accumulate是一个累加函数，把数组中每个字母的出现次数（num）依次处理，最终合成一个整体的哈希特征值 acc
        auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t {
            // 使用 accumulate 遍历数组，将 26 个数字混合成一个唯一的 size_t 类型哈希值
            return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
                // 位运算：左移一位并异或当前数字的哈希值，减少冲突
                return (acc << 1) ^ fn(num);
            });
        };

        // 键（Key）：26个字母的计数数组；值（Value）：属于该分组的字符串集合
        unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
        for (string& str: strs) {
            // 初始化一个长度为 26 的数组，全为 0
            array<int, 26> counts{};
            int length = str.length();

            // 遍历当前字符串的每个字符
            for (int i = 0; i < length; ++i) {
                // str[i] - 'a' 将字母转化为 0-25 的索引（例如 'b' 变成 1）
                counts[str[i] - 'a'] ++;
            }

            // 将原始字符串放入对应的“计数特征”组里
            // 只要两个词是字母异位词，它们的 counts 数组内容就完全一样
            mp[counts].emplace_back(str);
        }
        vector<vector<string>> ans;
        // 遍历哈希表，把每一组（value 部分）存入结果数组中
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

📊 复杂度分析

1、排序解法

时间复杂度： $O(nk\ logk)$ ，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 $O(k\ logk)$ 的时间进行排序以及 $O(1)$ 的时间更新哈希表，因此总时间复杂度是 $O(nk\ logk)$ 。
空间复杂度： $O(nk)$ ，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

2、计数解法

时间复杂度： $O(n(k+∣Σ∣))$ ，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度， $Σ$ 是字符集，在本题中字符集为所有小写字母， $∣Σ∣=26$ 。需要遍历 n 个字符串，对于每个字符串，需要 $O(k)$ 的时间计算每个字母出现的次数， $O(∣Σ∣)$ 的时间生成哈希表的键，以及 $O(1)$ 的时间更新哈希表，因此总时间复杂度是 $O(n(k+∣Σ∣))$ 。
空间复杂度： $O(n(k+∣Σ∣))$ ，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的最大长度， $Σ$ 是字符集，在本题中字符集为所有小写字母， $∣Σ∣=26$ 。需要用哈希表存储全部字符串，而记录每个字符串中每个字母出现次数的数组需要的空间为 $O(∣Σ∣)$ ，在渐进意义下小于 $O(n(k+∣Σ∣))$ ，可以忽略不计。