mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
31 lines
1.2 KiB
Markdown
31 lines
1.2 KiB
Markdown
# [318. Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/)
|
||
# 思路
|
||
|
||
给定单词数组，求两个没有相同字母的单词的长度之积的最大值。因此此题关键就是如何快速判断两个单词是否有相同字母。
|
||
|
||
由于题目说了只可能是小写字母，小写字母只有26个，那么我们可以考虑用一个32位的int变量表示某个单词的字母出现情况，
|
||
这样判断两个单词是否有相同字母就可以简单使用与操作。
|
||
|
||
是个二重循环，因此时间复杂度O(n^2)；需要开辟一个数组存放每个单词的int表示，因此空间复杂度O(n)。
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int maxProduct(vector<string>& words) {
|
||
int res = 0;
|
||
vector<int>bits(words.size(), 0);
|
||
for(int i = 0; i < words.size(); i++){
|
||
for(int j = 0; j < words[i].size(); j++)
|
||
bits[i] |= (1 << (words[i][j] - 'a'));
|
||
|
||
for(int k = 0; k < i; k++)
|
||
if(!(bits[i] & bits[k]))
|
||
res = max(res, int(words[i].size() * words[k].size()));
|
||
}
|
||
|
||
return res;
|
||
}
|
||
};
|
||
```
|