二进制表示思想
暴力枚举每个单词是$O(N^2)$,再加上每次判断两个字符串是否有重复字母时间复杂度$O(M)$,总时间复杂度$O(N^22M)$。
优化:主要是对于两个字符串判断是否有重复字母进行优化。
因为只有26个字母,利用二进制表示的思想,将每个word用int来表示,a-z映射成一个int的二进制位0-25位,若word的某个字母出现,则对应的二进制位表示为1。
这样表示,则判断两个字符串是否有重复字母的问题就变成了判断两个数字二进制位是否存在对应位都为1的,用
&
运算判断时间能达到$O(1)$
时间复杂度$O(N^2)$,空间复杂度$O(N)$
AC代码
class Solution {
public:
int maxProduct(vector<string>& words) {
//转二进制表示
vector<int> num_words;
for (auto word : words) {
int num = 0;
for (int i = 0 ; i < word.size() ; i ++) {
num |= 1 << (word[i] - 'a');
}
num_words.push_back(num);
}
//枚举
int res = 0;
for (int i = 0 ; i < words.size() ; i ++) {
for (int j = i + 1 ; j < words.size() ; j ++) {
if (!(num_words[i] & num_words[j]))
res = max(res, (int)words[i].size() * (int)words[j].size());
}
}
return res;
}
};