Total Accepted: 19855 Total Submissions: 50022 Difficulty: Medium
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".
Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".
Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
Hide Tags
题解：
find the maximum value of
length(word[i]) * length(word[j]) where the two words do not share common letters.重点在于 判断 有没有重复的字母
由于只有小写字母（26个），所以用 状压，位运算 （与）即可
class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
vector <int> len;
vector <int> contain;
int i,j;
int l;
for(i = ;i < n;i++){
l = words[i].length();
len.push_back(l);
int tmp = ;
for(j = ;j < l;j++){
int x = words[i][j] - 'a';
tmp |= ( << x);
}
contain.push_back(tmp);
}
int re = ;
for(i = ;i < n;i++){
for(j = i + ;j < n;j++){
if(contain[i] & contain[j]){
continue;
}
re = max(re,len[i] * len[j]);
}
}
return re;
}
};