318-maximum-product-of-word-lengths.md

318. Maximum Product of Word Lengths - 最大单词长度乘积

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

示例 1:

输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:

输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

示例 3:

输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。

---

题目标签：Bit Manipulation

题目链接：LeetCode / LeetCode中国

题解

如何判断两个单词没有相同的字母呢？

比较快的做法是用位运算，将单词表示为bitmap的形式，然后两个单词做与运算，如果等于0就没有相同的字母。

Language	Runtime	Memory
cpp	24 ms	1.1 MB

class Solution {
public:
    int maxProduct(vector<string>& words) {
        if (words.size() < 2) {
            return 0;
        }
        vector<int> arr;
        vector<int> lens;
        for (string word : words) {
            int i = 0;
            int l = 0;
            for (char c : word) {
                i |= (1 << (c - 'a'));
                l++;
            }
            arr.push_back(i);
            lens.push_back(l);
        }
        int res = 0;
        for (int i = 0; i < (int)arr.size() - 1; ++i) {
            for (int j = i + 1; j < (int)arr.size(); ++j) {
                // Note: the priority of & is lower than ==
                if ((arr[i] & arr[j]) == 0) {
                    res = max(res, lens[i] * lens[j]);
                }
            }
        }
        return res;
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();