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

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

그대로 읽어도, 거꾸로 읽어도 같은 것을 의미한다.

hash map을 사용해서, order 시킨 string을 key값으로 넣어준다.

그리고 value값으로 기존의 값을 vector로 넣어준다.

class Solution {
public:
	vector<vector<string>> groupAnagrams(vector<string>& strs) {
		std::unordered_map<string, vector<string>> um;
		for (int i = 0; i < strs.size(); ++i)
		{
			string order = strs[i];
			sort(order.begin(), order.end());
			um[order].emplace_back(strs[i]);
		}
		vector<vector<string>> vStrings;
		for (auto map : um)
		{
			vStrings.emplace_back(map.second);
		}
		return vStrings;
	}
};

Runtime: 32 ms, faster than 93.81% of C++ online submissions for Group Anagrams.

Memory Usage: 20.5 MB, less than 58.68% of C++ online submissions for Group Anagrams.

각각의 strs[i]를 정렬하는 시간 m(logm)

hash map 에 넣어주는 시간. n

nm(logm) 의 time complexity

각각의 strs[i] 의 size m

hash map에 n번 들어가야 하니까 O(nm) 의 space complexity