318. Maximum Product of Word Lengths

今天的题目是318. Maximum Product of Word Lengths。

比较简单的一道的题目，由于 word 只由26种小写字母组成，所以我们
可以利用一个 32 位的整数中前26位存储每个 word 中是否出现够某个字符。
进而，可以快速的判断两个 word 是否含有公共字母。然后两两比较，找出
不含有公共字母的单词对，并计算单词对的长度乘积，求解得到最大单词长度乘积了。

unsigned word2bits(const string &word) {
    unsigned res = 0;
    for(auto c: word) {
        res |= 1 << (c-'a');
    }
    return res;
}
int maxProduct(vector<string>& words) {
    int size = words.size();
    if (!size) return 0;

    vector<unsigned> bitmap(size);
    for(int i = 0; i < size; i++) {
        bitmap[i] = word2bits(words[i]);
    }
    int res = 0;
    for(int i = 0;i < size; i++) {
        for(int j = i + 1;j < size; j++) {
            if ((bitmap[i] & bitmap[j]) == 0) {
                res = max(res, int(words[i].size() * words[j].size()));
            }
                
        }
    }
    return res;
}

BTW，其实一开始我以为它是需要优化到O(nlogn)才能 AC 的。