if 0


给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。
假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

示例 1:
输入: words = [“abcw”, “baz”, “foo”, “bar”, “fxyz”, “abcdef”]
输出 : 16
解释 : 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符，且长度的乘积最大。
示例 2 :
输入 : words = [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”]
输出 : 4
解释 : 这两个单词为 “ab”, “cd”。
示例 3 :
输入 : words = [“a”, “aa”, “aaa”, “aaaa”]
输出 : 0
解释 : 不存在这样的两个单词。
#endif

  1. #include <iostream>
  2. #include <vector>
  4. using std::vector;
  5. using std::string;
  7. int maxProduct(vector<string>& words) {
  9.     int n = words.size();
  11.     int* masks = new int[n];
  12.     memset(masks, 0, sizeof(int)*n );
  13.     int* lens = new int[n];
  14.     //预先计算和长度
  15.     for (int i = 0; i < n; ++i)
  16.     {
  17.         for (char c : words[i])
  18.         {
  19.             masks[i] |= 1 << (c - 'a');   //这一句是将所有掩码取得
  20.         }
  21.         lens[i] = words[i].size();
  22.     }
  23.     //保存最大的乘积
  24.     int res = 0;
  25.     //两层遍历
  26.     int curr = 0;
  27.     for (int i = 0; i < n; ++i)
  28.     {
  29.         for (int j = i + 1; j < n; ++j)
  30.         {
  31.             curr = lens[i] * lens[j];
  32.             if (curr > res)
  33.             {
  34.                // std::cout<<curr<<" "<<i<<","<<j<<" "<<(masks[i]& masks[j])<<std::endl;
  36.                 if ((masks[i] & masks[j]) == 0)
  37.                     res = curr;
  38.             }
  39.         }
  40.     }
  41.     return res;
  42. }
  45. int main()
  46. {
  47.     vector<string> words{ "abcw", "baz", "foo", "bar", "fxyz", "abcdef" };
  48.     std::cout<<maxProduct(words);
  49. }