剑指 Offer II 005. 单词长度的最大乘积

题目链接：剑指 Offer II 005. 单词长度的最大乘积

方法：转化为二进制位 + 位运算

解题思路

• 将 \(words[i]\) 字符串中包含的字母转换为二进制位上的 \(1\)，字符 'a' 对应二进制中的第 \(0\) 位上的 \(1\)，这样每个字符串就对应一个二进制数。
• 通过两个字符串的二进制数进行 '&' 运算，结果为 \(0\) ，表示无重复字符，否则则表示有。

代码

class Solution{
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> mask;
        for (auto &str : words) {
            int cur = 0;
            for (auto &c : str) {
                cur |= (1 << (c - 'a'));
            }
            mask.push_back(cur);
        }
        int ans = 0;
        for (int i = 0; i < n; i ++ ) {
            for (int j = i + 1; j < n; j ++ ) {
                if ((mask[i] & mask[j]) == 0) {
                    int len = words[i].length() * words[j].length();
                    ans = max(ans, len);
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(L + n^2)，L 为所有字符串长度总和，n 为字符串数量\)；
空间复杂度：\(O(n)\)。