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;
    }

};