0318. Maximum Product of Word Lengths¶
题目信息¶
- 题号:
0318
- 难度:
Medium
- 主题:
字符串数组、字符集合、两两选择、最大乘积
- 原题:
- 重点:
两个单词不能共享任何字母、同一字母重复出现仍只表示共享、无合法单词对时返回 0
题目重述¶
给定字符串数组 words,每个字符串只包含小写英文字母。从数组中选择两个不同下标的单词,要求二者没有任何共同字母,并计算它们长度的乘积。返回所有合法单词对能够得到的最大乘积。
words 的长度位于 [2, 1000],每个单词长度位于 [1, 1000]。判断是否共享字符只关心字母是否出现,不关心出现次数;若任意两个单词都至少共享一个字母,则返回 0。
自建示例¶
最长的两个单词恰好没有公共字母:
输入:words = ["ab", "cde", "afg", "hi"]
输出:9
解释:"cde" 与 "afg" 的字符集合互不相交,长度乘积为 3*3=9;其他合法单词对的乘积都不超过 9。
不存在合法单词对:
输入:words = ["aa", "ab", "ac"]
输出:0
解释:任意两个单词都包含字母 a,因此没有一对满足条件。
把每个单词压成 26 位集合¶
一个单词是否包含某个字母只需要一个布尔状态,因此可以用整数的第 c - 'a' 位表示字母 c 是否出现。两个单词的掩码按位与为零,当且仅当它们没有公共字母;单词内部同一字母重复出现不会改变掩码。
先按掩码记录同一字符集合下的最长单词。相同掩码的两个单词不可能合法配对,较短者也不可能在与第三个单词的乘积中优于同掩码的较长者,因此保留每个掩码的最大长度即可。最后枚举不同掩码的两两组合,更新合法乘积。
C++ 实现¶
class Solution {
public:
int maxProduct(std::vector<std::string>& words) {
std::unordered_map<int, int> longest;
for (const std::string& word : words) {
int mask = 0;
for (char c : word) {
mask |= 1 << (c - 'a');
}
longest[mask] = std::max(longest[mask],
static_cast<int>(word.size()));
}
std::vector<std::pair<int, int>> groups(
longest.begin(), longest.end());
int answer = 0;
for (int i = 0; i < static_cast<int>(groups.size()); ++i) {
for (int j = i + 1;
j < static_cast<int>(groups.size()); ++j) {
if ((groups[i].first & groups[j].first) == 0) {
answer = std::max(answer,
groups[i].second * groups[j].second);
}
}
}
return answer;
}
};
代码分析¶
位运算一次就能完成字符集合相交判断,避免对每一对单词重复扫描字符。压缩同掩码单词不会改变最优值,且在重复字符集合较多时减少配对数量。设保留下来的掩码数为 u,建掩码需要 O(所有单词字符总数),配对需要 O(u^2),额外空间为 O(u)。