Leetcode 318 Solution

This article provides solution to leetcode question 318 (maximum-product-of-word-lengths)
Categories:
Tags:
Access this page by simply typing in "lcs 318" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/maximum-product-of-word-lengths

Solution

class Solution {
public:
    int getmask(const string& str)
    {
        int res = 0;

        for (auto it = str.begin(); it != str.end(); it++)
        {
            res |= 1 << (*it - 'a');
        }

        return res;
    }

    int maxProduct(vector<string>& words) {
        int res = 0;
        vector<int> a(words.size());

        for (int i = 0; i < words.size(); i++)
            a[i] = getmask(words[i]);

        for (int i = 0; i < words.size(); i++)
        {
            int l1 = words[i].size();

            for (int j = i + 1; j < words.size(); j++)
            {
                int l2 = words[j].size();

                if ((a[i] & a[j]) == 0)
                    res = max(res, l1 * l2);
            }
        }

        return res;
    }
};