Maximum Product of Word Lengths
給定一個(gè)字符串?dāng)?shù)組vector<string> words, 求兩個(gè)詞的長(zhǎng)度的最大乘積，這兩個(gè)詞必須不能包含同樣的字母
很容易想到的就是比較兩個(gè)詞包含的字母暂论，我們可以用一個(gè)32位（32位可以容納26個(gè)字母）的數(shù)字記錄一個(gè)單詞包含的字母礁竞。對(duì)于兩個(gè)詞只需要對(duì)兩個(gè)詞對(duì)應(yīng)的二進(jìn)制mask做and運(yùn)算，如果沒有相同的字母戳表，嘗試更新result
對(duì)于每個(gè)詞的mask，我們用一個(gè)int數(shù)組來存放
ab: 00...0000011
cdfg 0...1101100
class Solution {
public:
int maxProduct(vector<string>& words) {
vector<int> masks(words.size(), 0);
int result = 0;
for (int i = 0; i < words.size(); i++) {
for (char c: words[i])
masks[i] |= 1 << (c - 'a');
for (int j = 0; j < i; j++) {
if (!(bits[i] & masks[j]))
result = max(result, (int)(words[i].size() * words[j].size()));
}
}
return result;
}
};
