2023年10月27日

Leetcode-字母异位词分组

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

**示例 1:**输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

**示例 2:**输入: strs = [""]输出: [[""]]

**示例 3:**输入: strs = ["a"]输出: [[“a”]]

提示：

  • 1 <= strs.length <= 104

  • 0 <= strs[i].length <= 100

  • strs[i] 仅包含小写字母

解题思路：

  1. 首先定义了一个自定义排序函数 mySort，它将输入的字符串按字母顺序进行排序，并返回排序后的字符串。

  2. 然后定义了一个自定义哈希函数 myHash，它使用给定的哈希种子值和字符串中的字符来计算哈希值。

  3. 在 groupAnagrams 函数中，创建了一个无序哈希映射 map，用于存储按字母组成相同的字符串的分组结果。

  4. 遍历输入的字符串数组 strs，对每个字符串进行排序得到 sorted_str，然后计算它的哈希值 hash_key。

  5. 将当前字符串 str 插入到哈希桶 hash_key 对应的向量中。

  6. 最后，遍历哈希映射 map，将每个哈希桶中的字符串列表添加到结果向量 res 中，并返回最终的结果。

class Solution {
public:
    std::string mySort(const std::string& a) {
        std::string b = a;
        std::sort(b.begin(), b.end());
        return b;
    }


    // 自定义哈希函数
    unsigned int myHash(const std::string& str) {
        const unsigned int seed = 131; // 更大的质数
        unsigned int hash = 0;


        for (char ch : str) {
            hash = hash * seed + ch;
        }


        return hash;
    }


    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        std::unordered_map<unsigned int, std::vector<std::string>> map;


        for (const auto& str : strs) {
            auto sorted_str = mySort(str);
            unsigned int hash_key = myHash(sorted_str);
            map[hash_key].emplace_back(str);
        }


        for (const auto& item : map) {
            res.emplace_back(item.second);
        }


        return res;
    }
};