318. Maximum Product of Word Lengths
描述
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
分析
这道题要求找出一个string组成的vector中两个不重复子串的长度之积的最大值，方法有两种:
1.穷举法
枚举所有可能，最后找出长度之积最大且不相交的两个字符串，这种方法很容易想到，但细节方面还是需要注意，这里我们考虑到题目要求中保证输入数据只含有小写字母，所以我们就用一个数组来进行映射操作。
代码如下:
class Solution {
public:
int maxProduct(vector<string>& words) {
int max=0;
for(int i=0;i<words.size();i++){
int k=0;
int map[26]={0};
int size_a=words[i].size();
while(k<words[i].size())
map[words[i][k++]-'a']=1;
for(int j=i+1;j<words.size();j++){
int m=0;
int size_b=words[j].size();
if(size_a*size_b>max){
while(m<words[j].size()){
if(map[words[j][m]-'a']==0)
m++;
else
break;
}
if(m==words[j].size())
max=size_a*size_b;
else
continue;
}
}
}
return max;
}
};
显然，多次的循环会极大地影响算法的时间性能，于是我们考虑换一个角度进行考虑。
我们只是想判断穷举过程中后一个字符串中的字母是否在前面的某个字符串中出现过，既然只是判断字母，那么我们可以用一个二进制位来保存字母的存在与否及其位置关系。
具体而言，我们需要一个长度为n的数组，n为vector的长度，之后对每个子串进行遍历，遍历过程中，需要将每一个字母映射到相应的二进制位上，之后，想要判断是否在之前出现过，只需要对两个子串对应的二进制数做AND运算，结果为0，则说明没有出现重复。
代码如下:
class Solution {
public:
int maxProduct(vector<string>& words) {
int size=words.size();
int max=0;
vector<int> word(size,0);
for(int i=0;i<words.size();i++){
for(int j=0;j<words[i].size();j++)
word[i]|=1<<(words[i][j]-'a');
}
for(int i=0;i<words.size();i++){
for(int j=i+1;j<words.size();j++){
if((word[i]&word[j])==0&&words[i].size()*words[j].size()>max)
max=words[i].size()*words[j].size();
}
}
return max;
}
};