318. 最大单词长度乘积

题目链接🔗: 318. 最大单词长度乘积

相同的字符有相同的字符.举个例子,比如"aaa"和 "bab"这两个字符串拥有字符有'字符解法就是对逐个字符进行比较,如果是这样的话,这就缺失了写这篇博文的意义.


这里我们使用比较巧妙的方法:位运算

先设定对于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
那么 那么 题目 根据 要求 要求 要求 要求 要求 没有 的 字符 字符 的 两 个 个 字符串 字符串 的 最大 最大 长度 乘积 乘积 乘积 乘积 只 需要 记录 记录 相同 字符 字符 组成 组成 的 字符串 长度 的 最 最 大 值 就 了 了 这里 这里 使用 使用 使用 去 去 去 实现 实现 实现 就 就

代码参考如下:

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;
    }
};