49.Group Anagrams¶
Tags: Medium
Hash Table
String
Links: https://leetcode.com/problems/group-anagrams/
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.
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
unordered_map<string, vector<int>> m;
int n = strs.size();
for (int i = 0; i < n; ++i){
string tmp = strs[i];
sort(tmp.begin(), tmp.end());
m[tmp].push_back(i);
}
vector<vector<string>> res;
for (auto & e : m) {
vector<string> v;
int len = e.second.size();
for (int i = 0; i < len; ++i) {
v.push_back(strs[e.second[i]]);
}
res.push_back(v);
}
return res;
}
};
题意是把拥有相同字母的单词组合在一起输出,那么一个很直接的判断方法就是对单词进行排序,那么相同字母组合的排序后一定相等,题目又要求输出原单词,那么就每次将单词复制一份再排序。
考虑到要合并同类,那么很容易想到用字典,这里值的部分不需要保存单词,浪费空间,并且复制字符串耗时间,只需要记录这个单词在数组中的下标即可。