题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例

示例 1:

1 2	输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1 2	输入: strs = [""] 输出: [[""]]

示例 3:

1 2	输入: strs = ["a"] 输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

思考

我开始尝试的方向是把字母数字和相同的字符串作为字母异位词 。但这明显不可行，相等的不一定包含相同字符。

于是看到这个提示是采用哈希表实现。哈希表的特点就是key-value存储，一个key可以存在多个value。那么如何得到这个key就是突破方向。

考虑到，字母异位词字母是一样的，只是顺序变了，它们还得共用同一个key。这个key就是字符排序后的字符串，例如，”eat”和”ate”，遍历字符串后，把字符排序后，两个是相等的**”aet”。所以这里字符排序就是相应的哈希函数**了：hash(x) = key，得到的该字符串可以作为哈希表的key值。然后把key对应的value都添加到哈希表。

源码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 创建一个哈希表
        unordered_map<string, vector<string>> mp;
        // 遍历字符串数组，提取每个字符串
        for (string &str : strs)
        {
            // 计算key值，即把value通过哈希函数处理后得到，这里是sort()函数
            string key = str;
            sort(key.begin(), key.end());
            // 把value添加
            mp[key].emplace_back(str);
        }
        // 遍历哈希表，把key对应的value值保存到结果数组res中
        vector<vector<string>> res;
        for (auto it = mp.begin(); it != mp.end(); ++it)
            res.emplace_back(it->second);
        return res;
    }
};

C++知识

emplace_back 接口

通常我们添加数据到数组是用push_back，这里使用的是emplace_back，作用是在容器的末尾添加一个新的元素，这个元素是通过调用构造函数在原地构造的，不需要触发拷贝构造和移动构造。因此，emplace_back比push_back更加高效，可以节省内存和时间。emplace_back的用法是：