题目描述
题目链接:318. Maximum Product of Word Lengths
Given a string array
words
, return the maximum value oflength(word[i]) * length(word[j])
where the two words do not share common letters. If no such two words exist, return0
.
例子
例子 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][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