49. 字母异位词分组

题目链接:

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

 

方法一：

创建map，其中key为字符串的字母，value为相同字母组合的字符串列表。

遍历strs，存入map中。最后再遍历map转换成vector形式。

1. class Solution { 2. public: 3. vector<vector<string>> groupAnagrams(vector<string>& strs) { 4. map<string, vector<string>> ret; 5. 6. for (auto& str: strs) { 7. string index = str; 8. sort(index.begin(), index.end()); 9. ret[index].push_back(str); 10. } 11. 12. vector<vector<string>> ans; 13. for (auto iter = ret.begin(); iter != ret.end(); ++iter) { 14. ans.push_back(iter->second); 15. } 16. return ans; 17. } 18. };

方法二：

优化方法一的做法，减少map到vector的转换。

Map的key值还是字符串的字母，value变成了应存入vector中位置的下表。

这样可以直接根据value存入对应的vector中，减少了一次拷贝操作。

1. class Solution { 2. public: 3. vector<vector<string>> groupAnagrams(vector<string>& strs) { 4. unordered_map<string, int> ret; 5. vector<vector<string>> ans; 6. 7. for (auto& str: strs) { 8. string index = str; 9. sort(index.begin(), index.end()); 10. auto iter = ret.find(index); 11. if (iter == ret.end()) { 12. ret[index] = ans.size(); 13. ans.push_back(vector<string>{str}); 14. } else { 15. ans[iter->second].push_back(str); 16. } 17. } 18. 19. return ans; 20. } 21. };