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/
题意
给定一个字符串数组,对它们按anagrams进行分组,anagrams 的意思是由颠倒字母顺序而构成的字。比如abc/acb/bac/bca/cab/cba是同一个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;
}
};
实际运行时间并没有变快反而还慢了4ms。有人说貌似对于数据范围比较小的时候,理论时间复杂度应该有一点“不稳定”。
参考
The end.
2019年2月17日 星期日