Code & Func

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

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

1
unsigned word2bits(const string &word) {
2
    unsigned res = 0;
3
    for(auto c: word) {
4
        res |= 1 << (c-'a');
5
    }
6
    return res;
7
}
8
int maxProduct(vector<string>& words) {
9
    int size = words.size();
10
    if (!size) return 0;
11

12
    vector<unsigned> bitmap(size);
13
    for(int i = 0; i < size; i++) {
14
        bitmap[i] = word2bits(words[i]);
15
    }
11 collapsed lines
16
    int res = 0;
17
    for(int i = 0;i < size; i++) {
18
        for(int j = i + 1;j < size; j++) {
19
            if ((bitmap[i] & bitmap[j]) == 0) {
20
                res = max(res, int(words[i].size() * words[j].size()));
21
            }
22

23
        }
24
    }
25
    return res;
26
}

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