Accidentally made a very fast program... why is it so fast?


  • 1
    W

    Here is the code

    typedef struct{
        int len;
        int mask;
    }wordInfo;
    
    int comparer(const void* a,const void* b){
        return ((wordInfo*)b)->len - ((wordInfo*)a)->len;
    }
    
    int maxProduct(char** words, int wordsSize) {
        wordInfo* wis=(wordInfo*)malloc(wordsSize*sizeof(wordInfo));
        int i;
        for(i=0;i<wordsSize;++i){
            char* p=words[i];
            wis[i].mask=0;
            while(*p){
                wis[i].mask|=1<<(*p-'a');
                ++p;
            }
            wis[i].len=p-words[i];
        }
        qsort(wis,wordsSize,sizeof(wordInfo),comparer);
        int max=0,m;
        int range=wordsSize-1;
        for(int i=0;i<range;++i){
            for(int j=i+1;j<wordsSize;j++){
                if(!(wis[i].mask&wis[j].mask)){
                    m=wis[i].len*wis[j].len;
                    if(m>=max){
                        max=m;
                        if(j<range)range=j;
                    }
                    break;
                }
            }
        }
        return max;
    }
    

    I just coded them without much seriousness, without even checking carefully its correctness. And I got a run time of 32 ms ! (it said I beats 100% c submissions...what?!)

    I think what I did to make it fast was just using some bit-wise trick and sorting before searching. I didn't count it on very much because it still has a complexity of O(N^2), I think.

    So what exactly makes it so fast?


  • 0
    M

    I think it's the sorting by word length and then initiating an early break to avoid computing scores that will always be less than the last one found? I tried something similar, but still have ~100 ms run times.


Log in to reply
 

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