题目链接🔗:318. 最大单词长度乘积
这道题可以学习的地方在于如何快速比较出两个字符串是否拥有相同的字符。举个例子，比如"aaa" 和 "bab" 这两个字符串拥有相同的字符 'a' 的，暴力的解法就是对逐个字符进行比较，如果是这样的话，这就缺失了写这篇博文的意义。
这里我们使用比较巧妙的方法：位运算
- 先设定对于26个字符a ~ z，我们设定使用 0 ~ 25 代表它们，即num = x - 'a'
- 那么对应的每个字符串，都可以由一个整数（看成二进制表示），比如 'acd' 可以用二进制1101表示
如果两个字符串不包含相同的字符，那么与操作的结果一定是0，比如
'acd'用二进制表示为1101，'efg' 用二进制表示结果为1110000，比如1110000 & 0001101 = 0这样双重for循环遍历就可以找到结果，时间复杂度为O(N^2)
优化
为什么会有优化呢？
对于本题的第三个实例可以看出，对于如果由相同字符组成的不同长度的字符串，这样遍历很显然无用而且超时的
我们可以想到，对于由相同字符组成的字符串，他们的二进制表示一定是一样的，比如'aa' 和 'aaa'，他们表示的结果都是0000 0001
那么根据题目的要求，求 没有相同的字符 的两个字符串的最大长度乘积，只需要记录相同字符组成的字符串长度的最大值就可以了，这里就使用map去实现
代码参考如下：
class Solution {
public:
int maxProduct(vector<string> &words) {
int len = words.size();
vector<int> mask(len, 0);
map<int, string> ma;
for (int i = 0; i < len; ++i) {
string cur = words[i];
int l = cur.length();
int total = 0;
for (int j = 0; j < l; ++j) {
total |= (1 << (cur[j] - 'a'));
}
if (ma.find(total) != ma.end()) {
if (ma[total].length() < l) {
ma[total] = cur;
}
} else {
ma[total] = cur;
}
}
int res = 0;
for (auto it = ma.begin(); it != ma.end(); ++it) {
for (auto next = it; next != ma.end(); ++next) {
if (it == next) {
continue;
}
if (!((it->first) & (next->first))) {
res = max(res, int((it->second.length()) * (next->second.length())));
}
}
}
return res;
}
};
Top comments (0)