48ms C++ code using hash and sort


  • 0
    Z
    const uint32_t MAXN = 10000;
    
    
    inline uint64_t Hash(const char *szStr)
    {
    
        uint8_t aucCounter[26] = {0};
        
        while (*szStr)
        {
            aucCounter[*szStr++ - 'a']++;
        }
        
        uint64_t ullHash = 0;
        for (uint32_t i = 0; i < 26; ++i)       //BKDRHash
        {
            ullHash = ullHash * 131 + aucCounter[i];
        }
        return ullHash;
    }
    
    struct tElem
    {
    
        uint64_t ullHash;
        string * pStr;
        
        bool operator < (const tElem &stAnother) const
        {
            return ullHash != stAnother.ullHash ? ullHash < stAnother.ullHash : *pStr < *stAnother.pStr ;
        }
    };
    
    
    class Solution {
    
    public:
        vector<vector<string>> & groupAnagrams(vector<string>& strs) {
            
            static tElem astElem[MAXN];
            static uint32_t aulCounter[MAXN];
            uint32_t ulElemTot = 0;
            uint32_t ulCounterTot = 0;
            
            static vector<vector<string>> s_Result;
    
            for (vector<string>::iterator Iter = strs.begin(); Iter != strs.end(); Iter++)
            {
                astElem[ulElemTot].ullHash = Hash(Iter->c_str());
                astElem[ulElemTot++].pStr    = &*Iter;
            }
            
            sort(astElem, astElem + ulElemTot);
            
            uint32_t i = 0, j = 0, k = 0;
            aulCounter[0] = 0;
            
            for (i = 0; i < ulElemTot; ++i)
            {
                if (i && astElem[i].ullHash != astElem[i - 1].ullHash)
                {
                    aulCounter[++j] = 1;
                }
                else
                {
                    aulCounter[j]++;
                }
            }
            
            ++j;
            s_Result.resize(j);
            
            j = k = 0;
             s_Result[0].resize(aulCounter[0]);
             
            for (i = 0; i < ulElemTot; ++i, ++k)
            {
                if (i && astElem[i].ullHash != astElem[i - 1].ullHash)
                {
                    ++j;
                    k = 0;
                    s_Result[j].resize(aulCounter[j]);
                }
                
                s_Result[j][k] = *astElem[i].pStr;
            }
    
            return s_Result;
        }
    };

  • -2
    W

    This is how C programmers write codes, not C++ programmers


  • 0

    Thanks for your sharing! BTW, nice idea.


Log in to reply
 

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