力扣Hot100---49.字母异位词分组

来了来了,今天的题目也来了

力扣Hot100---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 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

解题思路

一开始我想的是利用^异或来解决,因为字符本质是数字,同一个串内字符之间异或顺序不影响结果,然后把异或结果作为key加入HashMap里面

代码大概是这样的:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 哈希表：key=字符串所有字符的异或值，value=该异或值对应的字符串列表
        unordered_map<int, vector<string>> xor_map;
        
        // 遍历每个字符串
        for (string s : strs) {
            int xor_result = 0;
            for (char c : s) {
                xor_result ^= c; // char本质是ASCII码，直接异或
            }
            // 将当前字符串加入对应异或值的分组
            xor_map[xor_result].push_back(s);
        }
        
        // 将哈希表中的分组转换为最终结果
        vector<vector<string>> result;
        for (auto& pair : xor_map) {
            result.push_back(pair.second);
        }
        
        return result;
    }
};

提交一下,试试

Emmmm..........

由于a^a还是等于a,也就是说abb和baa这两个串得到的key是一样的,显然是哈希冲突了.

此时大脑已经燃尽,我们来翻看一下官方的题解

忘记了字符串可以排序了

那我们再看看题目分析一下,当一个串内字符都相同的时候,排序后的串是一样的,这个时候我们把排序之后的串作为哈希表的key,这样可以避免上面遇到的问题

代码如下

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
	// 哈希表：key=排序后的字符串，value=对应的字符串列表
        unordered_map<string, vector<string>> m;
        for (string& s : strs) { //遍历并排序串
            string ss = s;
            ranges::sort(ss);
            m[ss].push_back(s);
        }
        vector<vector<string>> result;
        result.reserve(m.size());//预先分配空间
        for (auto& [_, value] : m) {
            result.push_back(value);
        }
        return result;
    }
};

时间空间复杂度在上面都有了,懒得写了

方法二就很神奇了,主要思路是我们创建一个26长度的数组来存储每个字符出现的次数,将这个数组作为哈希表的key存入,这个数组大概长这样

那按照这个方法,我们分析一下时间复杂度

遍历整个字符串数组需要O(n)的时间,每个字符计算下标需要O(m),还需字符集长度K的时间来生成哈希表的key,总的时间复杂度就是O((k+m)n)

空间上,我们使用了字符集数组作为key,长度为K,存储字符串需要n*m长度的空间,因此总的空间复杂度就是O(n(k+m))

参考资料

力扣官方题解---49.字母异位词分组