题目描述

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

样例

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

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

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

算法

(暴力枚举) $O(\max(n^2, nL))$

1. 预处理出每个单词的二进制数字表示，二进制表示一共有 26 位，如果该单词含有字母 a，则第 0 位为 1，依次类推。
2. 暴力枚举单词对，如果两个单词的 按位与(&) 为 0，则这两个单词可以被选择，求长度的乘积和最大值作比较即可。

时间复杂度

• 预处理二进制数字表示需要 $O(nL)$ 的时间，其中 $L$ 为单词的最大长度。
• 暴力枚举单词对需要 $O(n^2)$ 的时间，故总时间复杂度为 $O(\max(n^2, nL))$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储每个单词的二进制表示。

C++ 代码

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size(), ans = 0;
        vector<int> val(n, 0);
        for (int i = 0; i < n; i++)
            for (auto &c : words[i])
                val[i] |= 1 << (c - 'a');

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int v = (val[i] & val[j]) ? 0 : words[i].length() * words[j].length();
                ans = ans < v ? v : ans;
            }

        return ans;
    }
};