318. Maximum Product of Word Lengths

Leetcode link

解题思路

题目要求我们在一个字符串数组中找出字符完全不同的两个字符串使其长度乘积最大

这个题目的难点分为两个部分：

• 比较两个字符串是否有相同字符
• 找出符合条件的字符串中乘积最大的答案

比较两个字符串是否有相同字符

因为字符串之可能是英文的小写字母，所以我们可以用一个 int 长度的空间来放它的位掩码，位掩码从右到左依次代表 a 到 z，如果位掩码为 1 则表示该字符有出现

举个例子：abd 可以认为是 1011，aadddef 可以认为是 111001

一旦我们建立了所有字符串的位掩码，就可以通过两两相与是否大于 0 来判断是否有相同字符了

找出符合条件的字符串中乘积最大的答案

这个问题我们直接简单的双重循环来做比较，另外维护一个 res 变量保存最大结果

C++

class Solution {
public:
    int maxProduct(vector<string>& words) {
        vector<int> bitMasks;
        for(string &word:words) {
            int bitMask = 0;
            for(char &c:word) {
                bitMask |= 1 << (c - 'a');
            }
            bitMasks.push_back(bitMask);
        }

        int res = 0;
        int len = words.size();
        for(int i = 0;i < len;i++) {
            for(int j = i + 1;j < len;j++) {
                if((bitMasks[i] & bitMasks[j]) > 0) {
                    continue;
                }
                int product = words[i].size() * words[j].size();
                res = max(product, res);
            }
        }

        return res;
    }
};