Leetcode 49.字母异位词分组

题目描述：

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

1
2
3
4
5
6
7

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

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序。

链接：

https://leetcode-cn.com/problems/group-anagrams

题目分析

  题目中要求我们给字符串分类，很容易可以想到哈希的思想。我们可以建立一个哈希表，把一组字母异位词放到同一个 key 里作为哈希表的值。那么如何选取 key 值呢？观察字母异位词的共同点，它们的字母是相同的，但排列不同，也即是说，经过排序，它们会变成同一个字符串。则我们可以将这个排序好的字符串作为这一组字母异位词的 key 值。遍历所有的字符串加入哈希表之后，哈希表中的每一个 key 即对于一组字母异位词，将哈希表转化为结果即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hashmap;
        for(string str: strs){
            string key = str;
            sort(key.begin(), key.end());
            hashmap[key].push_back(str);
        }

        vector<vector<string>> result;
        for(auto it = hashmap.begin(); it != hashmap.end(); it++){
            result.push_back(it->second);
        }
        return result;
    }
};

  时间复杂度：$O(nk\log k)$，其中 $n$ 是字符串的个数，$k$ 是字符串的长度。因为我们总共需要添加 $n$ 个字符串，而每个字符串需要 $O(k\log k)$ 的时间排序，$O(1)$ 的时间加入到哈希表中，$O(k)$ 的时间复制到结果中。因此最后的总时间复杂度为 $O(nk\log k)$。
  空间复杂度：$O(nk)$，其中 $n$ 是字符串的个数，$k$ 是字符串的长度。也即哈希表的开销。

官方题解

  官方题解中将字符串加入到 vector 中的使用的函数都是 emplace_back，通过搜索学习发现原来是 C++11 的新特性，这个函数是将参数而不是对象传递给构造函数，而构造函数直接在容器空间中构造元素，因此省去了一次构造临时对象的过程，减少了内存开销。