题目
给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
示例 1：
1
2
3
| 输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16
解释：这两个单词为 "abcw", "xtfn"。
|
示例 2：
1
2
3
| 输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4
解释：这两个单词为 "ab", "cd"。
|
示例 3：
1
2
3
| 输入：words = ["a","aa","aaa","aaaa"]
输出：0
解释：不存在这样的两个单词。
|
提示：
2 <= words.length <= 10001 <= words[i].length <= 1000words[i] 仅包含小写字母
解答
想的时候就准备用26位的位运算去代表一个字符串，然后在与运算看有没有相同字母，没想到答案也是这么做的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int maxProduct(vector<string>& words) {
int length = words.size();
vector<int> masks(length);
for (int i = 0; i < length; i++) {
string word = words[i];
int wordLength = word.size();
for (int j = 0; j < wordLength; j++) {
masks[i] |= 1 << (word[j] - 'a');
}
}
int maxProd = 0;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if ((masks[i] & masks[j]) == 0) {
maxProd = max(maxProd, int(words[i].size() * words[j].size()));
}
}
}
return maxProd;
}
};
|
