C++ O(N^2) Solution Using Bit Manipulation


  • 1
    N
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> bitWords(n, 0);
        size_t maxLenProd = 0;
        
        for(int i=0; i<n; ++i){
            for(int j=0; j<words[i].length(); ++j){
                bitWords[i] |= (1<<(words[i][j]-'a'));
            }
        }
        
        for(int i=0; i<n-1; ++i){
            for(int j=i+1; j<n; ++j){
                if( (bitWords[i]&bitWords[j]) == 0){
                    maxLenProd = max(maxLenProd, words[i].length()*words[j].length());
                }
            }
        }
        return maxLenProd;
    }

Log in to reply
 

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