Two clean solutions C++


  • 0

    Solution 1. Straight forward, 315ms

        int maxProduct(vector<string>& words) {
            int maxlen = 0;
            for(int i = 0; i < words.size(); i++){
                for(int j = i+1; j < words.size(); j++){
                    int len = words[i].size() * words[j].size();
                    if(len <= maxlen) continue;
                    if(noCommon(words[i], words[j]))
                        maxlen = max(maxlen, len);
                }
            }
            return maxlen;
        }
        
        bool noCommon(string a, string b){
            for(auto c: a)
                for(auto x: b)
                    if(c == x) return false;
            return true;
        }
    

    Solution 2. Bit Manipulation, 43ms

        int maxProduct(vector<string>& words) {
            int maxlen = 0;
            vector<int>value(words.size());
            for(int i = 0; i < words.size(); i++)
                for(auto c: words[i])
                    value[i] |= 1<<(c-'a');
            
            for(int i = 0; i < words.size(); i++)
                for(int j = i+1; j < words.size(); j++)
                    if((value[i] & value[j]) == 0 && words[i].size() * words[j].size() > maxlen) 
                        maxlen = words[i].size() * words[j].size();
            return maxlen;
        }
    

Log in to reply
 

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