参考文献
ref{:target=”_blank”}
复杂度 O(n^2L), 位运算预处理后优化到 O(n^2L)
C++ 代码
class Solution {
public:
// 朴素解法: 复杂度 O(n^2*L), 位运算预处理后优化到 O(n^2*L)
int maxProduct(vector<string>& words) {
int n = words.size();
vector<int> words_bit(n);
// 预处理
for(int i=0; i<n; ++i){
const string& str = words[i];
for(char c : str)words_bit[i] |= 1 << (c - 'a');
}
// 计算
int res = 0;
for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++j){
if(words_bit[i]&words_bit[j])continue;
res = max(res, (int)words[i].size() * (int)words[j].size());
}
}
return res;
}
};