O(MN) time and O(N) space solution.


  • 0
    L

    N=number of strings, M=average number of chars in each string.

    the code is a little bit long, but this uses O(N) space assuming unordered_map uses space linear to the number of keys. Space excludes the space needed for the solution.

    Runtime is O(M*N) as each char is processed.

    Took ~100ms to be judged.

    struct key{
        int freq[26];
        int hash;
        bool operator==(const key&k2)const{
            int i,j;
            if(k2.hash!=hash)return false;
            for(i=0;i<26;i++)
                if(freq[i]!=k2.freq[i])return false;
            return true;
        }
    };
    namespace std{
        template<> struct hash<key> {
            size_t operator()(const key&k)const {
                return k.hash;
            }
        };
    };
    typedef unordered_map<key,int> mapt;
    class Solution {
        public:
        key calc(const string&s){
            key k={0};
            int i,j;
            for(i=0;i<s.size();i++){
                k.freq[s[i]-'a']++;
            }
            for(i=0;i<26;i++){
                k.hash = k.hash*31 + k.freq[i];
            }
            return k;
        }
        vector<string> anagrams(vector<string> &strs) {
             int i,j;
             vector<string> r;
             mapt map;
             for(i=0;i<strs.size();i++){
                 key k=calc(strs[i]);
                 pair<mapt::iterator,bool> p=map.emplace(make_pair(k,i));
                 if(!p.second){//already inserted
                     r.emplace_back(strs[i]);
                     int&idx=(p.first)->second;
                     if(idx>=0){
                        r.emplace_back(strs[idx]);
                        idx = -1;
                     }
                 }
             }
             return r;
        }
    };

Log in to reply
 

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