# LeetCode49. Group Anagrams（模拟）

## 2019 年 02 月 17 日 • 阅读: 941 • LeetCode • 阅读设置

### LeetCode49. Group Anagrams（模拟）

• Medium
• Accepted：290,927
• Submissions：655,421

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.

### 链接

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

### 题解

• 之前我们对anagram的处理是使用一个计数数组来进行判断，比如LeetCode438. Find All Anagrams in a String（滑动窗口
• 回到这道题，我们可以先对所有的字符串进行排序，因为anagram排序后是同一个字符串，然后对排序后相同的字符串保存起来即可，时间复杂度$O(n*mlogm)$（m指字符串长度）
• 因为全是小写字母，所以可以对字符串进行计数排序，然后再对相同字符串进行保存，时间复杂度$O(n*m)$

### 代码

• Runtime: 56 ms, faster than 69.04% of C++ online submissions for Group Anagrams.
• Memory Usage: 20.5 MB, less than 100.00% of C++ online submissions for Group Anagrams.
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map <string, vector<string>> umap;
vector<vector<string>> ans;
for (string s : strs)
{
string t = s;
sort(t.begin(), t.end()); // 排序后相同的放到一起
umap[t].push_back(s);
}
for (auto it : umap)
ans.push_back(it.second);
return ans;
}
};
• Runtime: 60 ms, faster than 48.78% of C++ online submissions for Group Anagrams.
• Memory Usage: 20.3 MB, less than 100.00% of C++ online submissions for Group Anagrams.
class Solution {
public:

string sortStr(string s) // 计数排序
{
int cnt[26] = {0};
for (int i = 0; i < s.length(); ++i)
cnt[s[i] - 'a']++;
string t = "";
for (int i = 0; i < 26; ++i)
t += string(cnt[i], 'a' + i);
return t;
}

vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map <string, vector<string>> umap;
vector<vector<string>> ans;
for (string s : strs)
umap[sortStr(s)].push_back(s);
for (auto it : umap)
ans.push_back(it.second);
return ans;
}
};

The end.
2019年2月17日 星期日