Group Anagrams
- 思路:练习C++中的hash
-
参考:yxc
-
题目
/*
* @lc app=leetcode id=49 lang=cpp
*
* [49] Group Anagrams
*
* https://leetcode.com/problems/group-anagrams/description/
*
* algorithms
* Medium (48.56%)
* Likes: 1994
* Dislikes: 128
* Total Accepted: 392.6K
* Total Submissions: 798.9K
* Testcase Example: '["eat","tea","tan","ate","nat","bat"]'
*
* Given an array of strings, group anagrams together.
*
* Example:
*
*
* Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
* Output:
* [
* ["ate","eat","tea"],
* ["nat","tan"],
* ["bat"]
* ]
*
* Note:
*
*
* All inputs will be in lowercase.
* The order of your output does not matter.
*
*
*/
- 代码
//创建矩阵:vector<vector<int>> Matrix(N, vector<int>(M));
//创建哈希表:unordered_map<string, vector<string>> hash;
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hash;
for (auto &str: strs)
{
string key = str; //把strs里面的每个str赋给key, 这里不应该用vector<string>么
// 注意这里的话是key只能赋值一个str,每赋值一个str,key就排序一次,之后再更新key
// 虽然最后的hash里面的key有很多,但是在这里每次只是赋值一个
sort(key.begin(), key.end()); //遍历每个str,并给每个str内部排序
//这里key.begin()是str第一个字母,key.end()-1是str最后一个字母
//排序之后,key有很多重复的
hash[key].push_back(str); // 把排序后的key加到hash中(k加入key不相同)
//每个key都对应加入为排序之前的字符串
//类似字典:例如:hash = {"aet":["ate","eat","tea"], "ant":["nat","tan"]}
// hash表添加的话:1.求出key, 2.hash[key].push_back(...);
}
vector<vector<string>> res; //新建一个二维字符串,用来存hash的第二部分
for (auto i = hash.begin(); i != hash.end(); i ++ ) //这里是auto, 另外不是i < hash.end()
// 这里面i是每一个在hash里的迭代器:"aet":["ate","eat","tea"]
res.push_back((*i).second); // 这里也可以用 i->second
return res;
}
};
赞
为啥最后res.push_back()里面是i.second
%%%