LeetCode 318. Maximum Product of Word Lengths (状态压缩)

题目大意:给出一些字符串,找出两个不同的字符串之间长度之积的最大值,但要求这两个字符串之间不能拥有相同的字符。(字符只考虑小写字母)。

题目分析:字符最多只有26个,因此每个字符串可以用一个二进制数来表示它含有哪些字符。

代码如下:

class Solution {
public:
int maxProduct(vector<string>& words) {
int maxn=0;
int *Bit=new int[words.size()];
fill(Bit,Bit+words.size(),0);
for(int i=0;i<words.size();++i){
int t=0;
for(int j=0;j<words[i].size();++j)
Bit[i]|=(1<<(words[i][j]-'a'));
for(int j=0;j<i;++j){
if(Bit[i]&Bit[j]) continue;
maxn=max(maxn,(int)(words[i].size()*words[j].size()));
}
}
delete []Bit;
return maxn;
}
};

  

上一篇:AI 经典书单 | 人工智能学习该读哪些书


下一篇:java解析json串常识