LeetCodeDay37|LeetCodeDay37 —— 字母异位词分组★★★ LeetCodeDay37—

49. 字母异位词分组描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例

输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明：所有输入均为小写字母。不考虑答案输出的顺序。

思路

暴力解法，将字符串数组中的字符串两两比较，相同的放在同一个Vector中
利用容器Map>, 将字符串String排序后作 Key, 同 Key 的字符串放在一个桶内。

// 超时算法 class Solution_49_OverTime { public: vector groupAnagrams(vector& strs) { vector ret; vector isTag; isTag.assign(strs.size(), false); for (int i = 0; i < strs.size(); ++i) { if (isTag[i]) continue; vector tmp; tmp.push_back(strs[i]); for (int j = i + 1; j < strs.size(); ++j) { if (isAnagram(strs[i], strs[j])) { tmp.push_back(strs[j]); isTag[j] = true; } } ret.push_back(tmp); } return ret; } bool isAnagram(string s1, string s2) { sort(s1.begin(), s1.end()); sort(s2.begin(), s2.end()); return s1 == s2; } }; // 错误的思路，字符和加位数并不能唯一确定字符串，如ac和bb class Solution_49_Error { public: vector groupAnagrams(vector& strs) { vector ret; unordered_map hash; vector weight; // 计算出每个字符串的权值 for (string str : strs) { int tmp = 0; for (char ch : str) { tmp += ch - 'a'; } weight.push_back(tmp * 10 + str.size()); } // 根据权重分配异位词 for (int i = 0; i < strs.size(); ++i) { auto iter = hash.find(weight[i]); if (iter == hash.end()) { hash[weight[i] = ret.size(); ret.push_back({strs[i]}); } else { ret[iter->second].push_back(strs[i]); } } return ret; } }; // string 作 key, 将对应的字符串放入数组中 class Solution_49 { public: vector groupAnagrams(vector& strs) { vector ret; unordered_map> mp; for(const string& str : strs){ string t = str; sort(t.begin(), t.end()); mp[t].push_back(str); } for(const auto& val : mp){ ret.push_back(val.second); } return ret; } };