C++ Solution using Bit Manipulation with Time Complexity O(max(O(nm), O(n^2))) where m is the average length of strings


  • 7
    Y
    class Solution {
    public:
        int maxProduct(vector<string>& words) {
            int ans = 0;
            if(words.size() < 2)
                return ans;
            int n = words.size();
            vector<int> val(n);
            for(int i = 0; i < n; ++ i){
                for(int j = 0; j < words[i].size(); ++ j){
                    int k = words[i][j] - 'a';
                    val[i] |= (1<<k);
                }
            }
            for(int i = 0; i < n - 1; ++ i){
                for(int j = i + 1; j < n; ++ j){
                    if((val[i]&val[j]) == 0){
                        ans = max(ans, (int)((int)words[i].size()*(int)words[j].size()));
                    }
                }
            }
            return ans;
        }
    };

  • 1
    class Solution {
    public:
        int maxProduct(vector<string>& words) {
            int v[words.size()], ret = 0;
            memset(v, 0, sizeof(v));
            for (int i = 0; i < words.size(); ++i){
                for (auto c: words[i]) v[i] |= 1 << (c - 'a');
                for (int j = 0; j < i; ++j){
                    if ((v[i] & v[j]) == 0) 
                        ret = max(ret, (int)words[i].size() * (int)words[j].size());
                }
            }
            return ret;
        } 
    };
    

    Inspired by your solution and I make the code shorter


  • 0
    Y

    Awesome! Keep going!


Log in to reply
 

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