LeetCode 0049 - Group Anagrams
# Hints
- STL
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
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 。
# 题解
显然每一个本质串都对应了一个 vector ,我们用 unordered_map
实现该映射,遍历所有字符串并求出其本质串,根据映射放入对应的 vector 中,最后将所有的 vector 取出即可。
# AC代码
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string> & strs) {
// 求解
unordered_map<string, vector<string>> ump;
for (auto & str : strs) {
// 获取有序串
string sorted = str;
sort(sorted.begin(), sorted.end());
// 记录
ump[sorted].push_back(str);
}
// 获取答案
vector<vector<string>> res;
for (auto it = ump.begin(); it != ump.end(); it ++) {
res.push_back(it->second);
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01