给你一个字符串数组 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
解释：不存在这样的两个单词。
|
方法一：
借助set实现暴力方法，但是会超时，方法行不通
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int maxProduct(vector<string>& words) {
int len = words.size();
int result = 0;
for(int i = 0;i < len;i++){
for(int j = i + 1;j < len;j++){
unordered_set<char>st;
bool flag = true;
for(auto ch : words[i]){
st.insert(ch);
}
for(auto ch : words[j]){
if(st.find(ch)!=st.end())flag = false;
}
if(flag)result = max(result, (int)words[i].length()*(int)words[j].length());
}
}
return result;
}
|
方法二：
转化为位运算，26个字母可以用int32位存下，如此可以成功了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int maxProduct(vector<string>& words) {
int len = words.size();
vector<int>nums(len,0);
for(int i = 0;i < len;i++){
for(auto ch : words[i]){
nums[i] = nums[i] | (1 << (ch-'a'));
}
}
int result = 0;
for(int i = 0;i < len;i++){
for(int j = i + 1;j < len;j++){
if( (nums[i] & nums[j]) == 0){
result = max(result,(int)words[i].size()*(int)words[j].size());
}
}
}
return result;
}
|
