O(N^2) straightforward C++ solution


  • 0
    C
    int maxProduct(vector<string>& words) {
        int size=words.size();
        int stlen[size];
        for(int i=0;i<size;i++) stlen[i]=words[i].length();
        int maxx=0;
        for(int i=0;i<size;i++){
            long maps=0;
            for(char c:words[i]) maps |= (1<<(c-'a'));
            int maxjlen=0;
            for(int j=i+1;j<size;j++){
                if(stlen[j]>maxjlen){
                    bool intersect=false;
                    for(char c:words[j]) { if((maps>>(c-'a'))&1) {intersect=true;break;}}
                    if(!intersect) maxjlen = stlen[j];
                }
            }
            maxx = max(maxx,stlen[i]*maxjlen);
        }
        return maxx;
    }
    

    The bit manipulation might not be necessary. Notice that in the inner loop, if the string length is less that the current longest one, then there is no need to perform the expensive "intersect" operation. This is the essential step for O(N^2) algorithm to avoid TLE.


Log in to reply
 

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