318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1: Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] Return 16 The two words can be "abcw", "xtfn".

Example 2: Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"] Return 4 The two words can be "ab", "cd".

Example 3: Given ["a", "aa", "aaa", "aaaa"] Return 0 No such pair of words.

题目大意:给出一个字符串数组，求出在这个数组中任意两个字符串的长度之积的最大值，要求这两个字符串不能包含相同的字符。 有种特殊的情况要考虑"aa", "bb",此时返回4；

解析：将每一个字符串转换成二进制的形式，int有32位 > 字母表的26位。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int res = 0;
        vector<int> mask(words.size());

        for(int i = 0; i < words.size(); i++){
            //将字符串转换成bitmap图
            for(auto &c:words[i])
                mask[i] |= 1 << (c-'a');

            for(int j = 0; j < i; j++){

                if((mask[i] & mask[j]) == 0)
                    res = max(res, (int)(words[i].size()*words[j].size()));
            }
        }

        return res;
    }
};

/*
 *采用map， map<mask, len>;
 */
class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<int, int> maxLen;
        int res = 0;
        for(auto &word:words){
            int mask = 0;
            for(auto &c:word){
                mask |= 1<<(c - 'a');
            }
            //此处要比较较大者的原因是为了避免"aabb"被"aab"覆盖掉
            maxLen[mask] = max(maxLen[mask], (int)word.size());

            for(auto m:maxLen){
                if((mask&m.first) == 0)
                    res = max(res, maxLen[mask] * m.second);
            }
        }
        return res;
    }
};