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