Halo

A magic place for coding

0%

LeetCode解题报告(384) -- 318. Maximum Product of Word Lengths

Problem

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.

Example 1:

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

Example 2:

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

Example 3:

1
2
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.

Analysis

  这道题给出了一个字符串数组,要求在里面找出两个字符串,使得这两个字符串长度的乘积最大,同时这两个字符串不能有相同的字符。题目的难点是如何快速判断出两个字符串是否拥有相同的字符。比较常规的做法可能是用一个map或者一个长度为26的数组去计算,其实更加快捷的方法应该是使用位运算。一个int就能表示一个单词中含有哪些字符。

  我们首先把words[i]中字符出现的情况转为一个int,然后再和[0, i - 1]之间的字符串对比,如果两者不存在相同的字符串,则计算一下两者长度的乘积,最后维护一个最大值即可。


Solution

  无


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int maxProduct(vector<string>& words) {
int result = 0;
int size = words.size();
vector<int> arr(size, 0);
for (int i = 0; i < size; i++) {
for (int j = 0; j < words[i].size(); j++) {
arr[i] |= (1 << (words[i][j] - 'a'));
}

for (int j = 0; j < i; j++) {
if (!(arr[i] & arr[j])) {
result = max(result, (int)(words[i].size() * words[j].size()));
}
}
}
return result;
}
};

Summary

  这道题目难度不算大,主要考察的点是用int去表示字符出现的次数,位运算在这一类场景中非常常用,具有运算效率高、节省空间等优点。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels