leetcode（哈希表）49.字母异位词分组（C++详细解释）DAY5

文章目录

1.题目
- 示例
- 提示
2.解答思路
3.实现代码
- 结果
4.总结

1.题目

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

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

示例

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

2.解答思路

需要定义的变量：
一定要有一个对应返回类型的answer。
设置一个哈希表hash。
(1) 键：存储字符串排序后的样子（唯一的）
(2) 值：每一类排序后一样的字符串放在同一类的分组里。（存储原来的字符串）
具体实现思路：
直接遍历整个strs，排序后一样的放到同一个hash表的键对应的值的位置。
存储到hash表后，在将每个值的答案存储到answer中。

补充知识点：
sort(s.begin(), s.end());//排序的类型需要是字符串
字符串更多成员函数详细介绍：C++字符串的常用操作函数全总结
unordered_map<string, vector< string >> hash; // 定义一个哈希表
hash[s].push_back(strs[i]);//将键s对应的值中添加一个vector< string >类型的元素strs[i]

遍历这种类型的hash表时：
auto 自动识别变量类型
pair表示哈希表中的一对键值对
其中pair.first表示哈希表中键的内容
其中pair.second表示哈希表中值的内容

3.实现代码

class Solution
{
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs)
    {

        vector<vector<string>> answer;//答案存放
        unordered_map<string, vector<string>> hash; // 定义一个哈希表
        // 键用来存放排序后的字符串，值用来存放原来字符串strs中的对应字符串

        for (int i = 0; i < strs.size(); ++i)
        {
            string s = strs[i];            
            sort(s.begin(), s.end());
            hash[s].push_back(strs[i]);
        }
        //此段for循环语句可使用如下代码代替
	// for (string &str : strs)
	// {
	//     string s = str;
	//     sort(s.begin(), s.end());
	//     hash[s].push_back(str);
	// }

        for (auto &pair : hash)
        { 
        /* pair表示哈希表中的一对键值对
        pair.first表示哈希表中键的内容
        pair.second表示哈希表中值的内容*/
            answer.push_back(pair.second);
        }

        return answer;
    }
};