这是一道字符串的题目,题目呢要求找到两个字符串没有重复的字符,且两者长度的乘积最大。暴力可以过。但是在比较字符串的时候可以用位运算,这样时间会大大缩短。
关于字符串,限制在只有小写字母的时候,位运算是可以运用起来,把一串字符用一个数字表示。两个字符串是否有重复,只需要位与一下就可以了
class Solution {
public:
vector<int> nums;
int maxProduct(vector<string>& words) {
nums = vector<int>(words.size());
for(int i=0;i<words.size();i++)
{
nums[i]=compute(words[i]);
}
int ans=0;
for(int i=0;i<words.size();i++)
{
for(int j=i+1;j<words.size();j++)
{
if(!(nums[i]&nums[j]))
{
if(ans < words[i].length()*words[j].length())
ans = words[i].length()*words[j].length();
}
}
}
return ans;
}
int compute(string s)
{
int bit = 0;
for(int i=0;i<s.length();i++)
bit |= (1<<(s[i]-'a'));
return bit;
}
};