C++ 128ms using bit manipulation


  • 1
    X
    class Solution {
    public:
        
        int max(int a, int b){
            return a< b? b : a;
        }
        
        int maxProduct(vector<string>& words) {
            int ans = 0;
            int size = words.size();
            if(size == 0){
                return ans;
            }
            vector<int> vec(size, 0);
            for(int i = 0;i < size; ++i){
                for(int j = 0;j < words[i].length(); ++j){
                    vec[i] |= 1 << (words[i][j] - 'a');
                }
            }
            for(int i = 0;i < size; ++i){
                for(int j = i;j < size; ++j){
                    if(vec[i] & vec[j]){
                        continue;
                    }
                    ans = max(ans, words[i].length() * words[j].length());
                }
            }
            return ans;
        }
    };

  • 0

    Thanks for your sharing,i got much from your idea,and through your codes,in the line of "for(int j=i;j<size;++j)",i think it would be better if we replace it by "for(int j=i+1;j<size;++j)".(Sorry for my poor English and thanks for your sharing again.)


  • 0
    X

    yes,you are right !
    thanks.


Log in to reply
 

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