Leetcode 49 Group Anagrams

2023-10-19 06:18

文章标签 leetcode group 49 anagrams

本文主要是介绍Leetcode 49 Group Anagrams，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

没做出来，自己的算法超时

class Solution {
public:typedef map<char, int>::iterator MIT;vector<vector<string>> groupAnagrams(vector<string>& strs) {// mark the workvector<vector<string> > ret;vector<map<char,int> > maps;size_t n = strs.size();for (size_t i = 0; i < n; ++i) {string str = strs[i];size_t strlen = str.size();map<char, int> tmp;for (size_t j = 0; j < strlen; ++j) {++tmp[str[j]];}        size_t k = 0;for (; k != maps.size(); ++k) {             if (maps[k].size() != tmp.size())  continue;MIT itmp = tmp.begin();for (; itmp != tmp.end(); ++itmp) {MIT imaps = maps[k].find(itmp->first);if (maps[k].end() == imaps || imaps->second != itmp->second)break;                        }if (itmp != tmp.end()) continue;else {ret[k].push_back(str);break;}}// 没找到if (k == maps.size()) {ret.push_back(vector<string>(1, str));maps.push_back(tmp);}}  for (size_t m = 0; m <ret.size(); ++m) {sort(ret[m].begin(), ret[m].end());}return ret;}
};

参考后

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map <string, multiset<string> > mp;for (auto str : strs) {// for (size_t i = 0; i != strs.size(); ++i) {//string str = strs[i];string keystr = sortStr(str);// sort(keystr.begin(), keystr.end());mp[keystr].insert(str);}vector<vector<string> > ret;for (auto m : mp) {ret.push_back(vector<string>(m.second.begin(), m.second.end()));}return ret;}private:
// sort 时间复杂度 O(n*logn)
// sortStr 时间复杂度 o(n)string sortStr(string s) {string ret;vector<int> flag(26, 0);for (auto ch : s) {++flag[ch - 'a'];}for (size_t i = 0; i < 26; ++i) {ret += string(flag[i], 'a' + i);}return ret;}
};