0%

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

题目描述

题目链接:318. Maximum Product of Word Lengths

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.

解题思路

这道题思路比较直观,对于每一个单词首先用一个哈希表来存储出现过的字母。然后进行二层遍历,比较所有可能的单词对,对每一对单词依次查看每个字母是否在两个单词出现过,如果没有的话则将其长度乘积与当前结果取最大值。最后返回结果即可,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <string>
#include <vector>

class Solution {
public:
int maxProduct(std::vector<std::string>& words) {
int n = words.size();
bool letters[n][26];
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

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions