## [Leetcode]318. Maximum Product of Word Lengths(C++)

### 题目描述

Given a string array `words`, return the maximum value of `length(word[i]) * length(word[j])` where the two words do not share common letters. If no such two words exist, return `0`.

### 例子

#### 例子 1

Input: `words = ["abcw","baz","foo","bar","xtfn","abcdef"]` Output: `16` Explanation: The two words can be `"abcw"`, `"xtfn"`.

#### 例子 2

Input: `words = ["a","ab","abc","d","cd","bcd","abcd"]` Output: `4` Explanation: The two words can be `"ab"`, `"cd"`.

#### 例子 3

Input: `words = ["a","aa","aaa","aaaa"]` Output: `0` Explanation: No such pair of words.

### Constraints

• `2 <= words.length <= 1000`
• `1 <= words[i].length <= 1000`
• `words[i]` consists only of lowercase English letters.

### 解题思路

``````#include <string>
#include <vector>

class Solution {
public:
int maxProduct(std::vector<std::string>& words) {
int n = words.size();
bool letters[n];
for (int i = 0; i < n; ++i) {
memset(letters[i], 0, 26);
std::string word = words[i];
for (char l : word) {
letters[i][l - 'a'] = true;
}
}

int max_len = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
bool shared = false;
for (int k = 0; k < 26; ++k) {
if (letters[i][k] && letters[j][k]) {
shared = true;
break;
}
}

if (!shared) {
max_len = std::max(
static_cast<int>(words[i].length() * words[j].length()),
max_len);
}
}
}
return max_len;
}
};
``````
• 时间复杂度: `O(n^2)`
• 空间复杂度: `O(n)`

GitHub 代码同步地址： 318.MaximumProductOfWordLengths.cpp