字母异位词分组

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

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

示例 1:

代码语言：javascript复制

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

示例 2:

代码语言：javascript复制

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

示例 3:

代码语言：javascript复制

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

提示：

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

思路

    哈希表的key是一组字母异位词共同拥有的字母，哈希表的value是这组字母异位词，对应2个要点：     每个单词的字母顺序不同，不能直接与key比较。取出一个单词后，首先需要另存一份，sort后与哈希表key值比较；     value是一个数组，key值相同后把单词插入至value

    mp[key].emplace_back(str);

复杂度

    时间复杂度: O(n)O(n)O(n)

    空间复杂度: unordered_map<string, vector>

代码语言：javascript复制

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string& str : strs) {
            string key = str;
            sort(key.begin(), key.end());
            //保证了不同顺序、相同字符的key值都一样
            mp[key].emplace_back(str);
            //value为一个向量时，向value插入值
        }
        vector<vector<string>> ans;
        //不初始化，size和capability都为0
        for (auto it = mp.begin(); it != mp.end();   it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

key string vector 数组 字符串

0 人点赞