116ms c++ solution use early pruning (faster than most O(N^2))


  • 15
    Z

    Sort the vector first according to the length of string. Then use some early pruning to fasten the process.

    The worst cases would still be O(N^2). It's faster than most O(N^2) solutions. I don't know whether we can do better. (Binary Search Seems Not work here) Any comments is welcomed.

    Update: We can use counting sort to improve the time complexity of sorting to O(N).

    class Solution {
    public:
        int maxProduct(vector<string>& words) {
            int s=words.size();
            if(s==0) return 0;
            vector<int> bit(s,0);
            sort(words.begin(), words.end(), compare);  //sort the vector from longest to shortest
            for(int i=0; i<s; i++){ //bit manipulation
                for(int j=0; j<words[i].size(); j++) bit[i] |=(1<<(words[i][j]-'a')); 
            }
            int maxlength=0;
            for(int i=0; i<s-1; i++){
                int si=words[i].size();
                if(si*si<=maxlength) break; //early pruning
                for(int j=i+1; j<s; j++){
                    int sj=words[j].size();
                    if(si*sj<=maxlength) break;  //early pruning
                    if((bit[i]&bit[j])==0) maxlength=si*sj;
                }
            }
            return maxlength;
        }
        static bool compare(string a, string b){
            return a.size()>b.size();
        }
    };

Log in to reply
 

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