Two C++ versions "beat 90%" (usually :P)


  • 0
    M

    The first code uses an O(n) counting sort assuming lower case a-z for the strings. This saves just a couple ms off of using the normal O(nlog(n)) string sort -- ~50ms according to powers that LeetCode.

            vector<vector<string>> groupAnagrams(vector<string>& strs)
            {
                if (strs.empty())
                    return{};
    
                // Counting sort is O(n) assuming a-z
                int freq[26] = { 0 };
                auto cntsort = [&](string& str)
                {
                    for (char ch : str) freq[ch - 'a']++;
    
                    int idx = 0;
                    for (int i = 0; i < 26; ++i)
                    {
                        while (freq[i]-- > 0)
                            str[idx++] = 'a' + i;
                        freq[i] = 0;
                    }
                };
    
                // Map sorted string to original index
                struct item
                {
                    bool operator<(const item& rhs) const
                    { return str < rhs.str; }
    
                    string str;
                    int idx;
                };
    
                auto N = static_cast<int>(strs.size());
    
                vector<item> items(N);
                for (int i = 0; i < N; ++i)
                {
                    items[i] = { strs[i], i };
                    cntsort(items[i].str);
                    
                    // to use regular sorting
                    // sort(begin(items[i].str), end(items[i].str));
                }
    
                sort(begin(items), end(items));
    
                vector<vector<string>> res(1, { strs[items[0].idx] });
                for (int i = 1; i < N; ++i)
                {
                    if (items[i].str != items[i - 1].str)
                    {
                        res.push_back({});
                    }
                    
                    res.back().push_back(strs[items[i].idx]);
                }
    
                return res;
            }
    

    And for good measure, simpler code using an unordered_map and normal sorting also runs in ~50ms;

        vector<vector<string>> groupAnagrams(vector<string>& strs)
        {
            if (strs.empty())
                return{};
    
            unordered_map<string, vector<string>> table;
            for (auto& str : strs)
            {
                auto key = str;
                sort(begin(key), end(key));
    
                table[move(key)].push_back(move(str));
            }
    
            vector<vector<string>> res(table.size());
            
            int idx = 0;
            for (auto& keyval : table)
            {
                res[idx++] = move(keyval.second);
            }
    
            return res;
        }
    

Log in to reply
 

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