[Rainbow] C++ implementation


  • 0

    Thanks to the post from jianchao.li.fighter .

    What I learned from the problem and the solution is that

        use multiset to sort the string array auto ....
    
        do not forget counting sort & radix sort & bucket sort 
    

    Here is the AC implementation:

      class Solution {
        public:
            vector<vector<string>> groupAnagrams(vector<string>& strs) {
                vector<vector<string>> result;
                unordered_map<string, multiset<string>> dict;
                for(auto str : strs){
                    string t=str;
                    //sort(t.begin(), t.end());
                    t=help(t);
                    dict[t].insert(str);
                }
                for(auto a : dict){
                    vector<string> temp(a.second.begin(), a.second.end());
                    result.push_back(temp);
                }
                return result;
            }
            
            /** use the count sort to accelerate the sorting process **/
            string help(string &s){
                vector<int> c(26, 0);
                int n=s.size();
                for(int i=0; i<n; i++)  c[s[i]-'a']++;
                int p=0;
                string t(n, 'a');
                for(int j=0; j<26; j++){
                    for(int i=0; i<c[j]; i++)
                        t[p++]+=j;
                }
                return t;
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.