C++ Bit Manipulation Solution


  • 0
    F

    The steps by follows:

    1. sort the words by length decreasing.
    2. set a mask to record the character by using bitwise OR in the first word
    3. in the rest of words, if it hasn't the same character in the mask by using bitwise AND, calculate the len, update the res
    4. be careful the para maxLenToComp, when there is a correct pair, update the maxLenToComp also, because the rest correct pairs must have less product than previous.
    class Solution {
    public:
        // compare function
        static bool comp(const string& lhs, const string& rhs)
        {
            return lhs.size() > rhs.size();
        }
    
        int maxProduct(vector<string>& words) {
            int res = 0;
            int maxLenToComp = words.size();
    
            sort(words.begin(), words.end(), comp);    // sort
            
            for (int i = 0; i < maxLenToComp; ++i)
            {
                int mask = 0;
                int sz1 = words[i].size();
                for (int j = 0; j < sz1; ++j)
                    mask |= (1 << (words[i][j] - 'a'));    // gene mask
                for (int k = i + 1; k < maxLenToComp; ++k)
                {
                    int sz2 = words[k].size();
                    bool isOk = true;
                    for (int j = 0; j < sz2; ++j)
                    {
                        if (mask & (1 << (words[k][j]) - 'a'))
                        {
                            isOk = false;
                            break;
                        }
                    }
                    // if there is a correct pair
                    if (isOk)
                    {
                        res = max(res, sz1 * sz2);    // update res
                        maxLenToComp = k;             // update maxLenToComp
                        break;
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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