Leetcode - 49. Group Anagrams

문제

같은 anagram인 문자열끼리 묶어라.

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

해결

정렬된 문자열을 키로 하고, original index를 value로 하는 해시테이블을 생성. 아래 주석 확인.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        vector<string> orig;
        unordered_map<string, vector<int>> freq;
        
        /* sort strs and save orig strs */
        for (auto &s: strs) {
            orig.push_back(s);
            sort(s.begin(), s.end());
        }
        
        /* generate freq hashtable (key:string, value: vector of index) */
        for (int i = 0; i < orig.size(); i++) {
            freq[strs[i]].push_back(i);
        }
        
        /* grouping via hashtable */
        for (auto f: freq) {
            vector<string> tmp;
            for (auto idx: f.second) /* f.second is a vector of index */
                tmp.push_back(orig[idx]);
            ret.push_back(tmp);
        }
        
        return ret;
    }
};