48 ms solution by creating hash function using prime numbers (sieve).


  • 0
    S
    class Solution {
    public:
        int prime[310],vis[2001];
        void sieve(){
            memset(vis,0,sizeof(vis));
            prime[0] = 2;
            int k = 1;
            for(int i=3;i<2000;i+=2){
                if(vis[i] == 0){
                    prime[k++] = i;
                    int j = i+i;
                    while(j<2000){
                        vis[j] = 1;
                        j+=i;
                    }
                }
            }
        }
        long long int hash(string s){
            long long int x=1;
            int n = s.size();
            for(int i=0;i<n;i++){
                x *= prime[s[i]];
            }
            return x;
        }
        vector<string> anagrams(vector<string>& strs) {
            sieve();
            map<long long int, vector<string> > m;
            vector<string> s;
            long long int x;
            int n = strs.size();
            if(n==0){
                return vector<string>();
            }
            for(int i=0;i<n;i++){
                x = hash(strs[i]);
                m[x].push_back(strs[i]);
            }
            map<long long int, vector<string> >::iterator it;
            for(it = m.begin();it!=m.end();it++){
                int y = it->second.size();
                if(y > 1){
                    s.insert(s.end(),it->second.begin(),it->second.end());
                }
            }
            return s;
        }
    };

Log in to reply
 

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