Cpp 60ms, beats 99.75%, 100% test cases passed


  • 0
    S
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int charToHash[26];
        int h = 1;
        for (int c=0; c< 26; ++c) {
            h = h * 31 + c;
            charToHash[c] = h;
        }
        
        unordered_map<int,int> hashToVectorIdx;
        vector<vector<string>> result;
        int resultIdx = 0;
        
        for (int i=0;i<strs.size();++i) {
            string s = strs[i];
            int hash = 0;
            for (int k=0;k<s.length();++k) {
                hash += charToHash[s[k] - 'a'];
            }
            if (hashToVectorIdx.find(hash) == hashToVectorIdx.end()) {
                result.push_back(vector<string>(1, s));
                hashToVectorIdx[hash] = resultIdx;
                ++ resultIdx;
            }
            else {
                result[hashToVectorIdx[hash]].push_back(strs[i]);
            }
        }
        
        for (vector<vector<string>>::iterator itr = result.begin(); itr != result.end(); ++itr) {
            sort(itr->begin(), itr->end());
        }
        return result;
    }

Log in to reply
 

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