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