题目来源
给一个字符串数组，判断不存在重复字符的两字符串的最大长度乘积。
我一开始想着用哈希记录下每个字符串有的各个字符，然后再和另外的比较，代码如下：
class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size(), res = 0;
for (int i=0; i<n-1; i++) {
unordered_map<int, int> maps;
int la = words[i].size();
for (int j=0; j<la; j++)
maps[words[i][j]]++;
for (int j=1; j<n; j++) {
bool commentLetter = false;
int lb = words[j].size();
for (int k=0; k<lb; k++)
if (maps.count(words[j][k]) != 0) {
commentLetter = true;
break;
}
if (!commentLetter)
res = max(res, la * lb);
}
}
return res;
}
};
可以AC，不过巨慢无比。看了下tags，用的位操作，代码如下：
class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size(), res = 0;
vector<int> mask(n);
for (int i=0; i<n; i++) {
for (char c : words[i])
mask[i] |= 1 << (c - 'a');
for (int j=0; j<i; j++) {
if (!(mask[i] & mask[j]))
res = max(res, static_cast<int>(words[i].size() * words[j].size()));
}
}
return res;
}
};
