318. 最大单词长度乘积
前言
「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。
这是本系列的第 4 篇题解，更多题解关注 Somnia1337@力扣。
题目描述
难度：🟡中等
给你一个字符串数组 words，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0。
输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16
解释：这两个单词为 "abcw", "xtfn"。输入：words = ["a","aa","aaa","aaaa"]
输出：0
解释：不存在这样的两个单词。题意理解
输入：String[]，一个字符串数组。
输出：int，两个字符串长度乘积的最大值，且这两个字符串不能有共同字母。
举例：对于输入 ["adf", "ab", "g"]，虽然 "adf" 与 "ab" 的长度乘积为 6，但是它们有共同字母 'a'，不满足要求，需返回 "adf" 与 "g" 的长度乘积 3。
解题思路
由于题目的限定，任意两字符串都有可能成为答案，因此需枚举所有字符串对，在满足要求时更新答案，时间复杂度不会低于 。
关键在于，如何快速判断两个字符串 a、b 是否含有共同字母。
几个不够优秀的方案
- 枚举：枚举
a的每个字符，反复遍历b，判断是否相同。 - 排序：对
a、b的字母分别排序，然后用双指针遍历一次。 - 字符统计：统计
a、b各自有哪些字符（存储到数组 / 哈希表内），再判断是否有重叠。
显然，这些方案的复杂度都太高，在题目 1000 个字符串、每个字符串最长为 1000 的条件下有超时的危险。
一个更好的方案
提示 1：如果能预处理 words，为每个字符串计算一个数值，就可以在 时间内完成比较。
提示 2：这个数值需要特异地标记字符串中每个字母的出现与否，不妨考虑用 0 标记某个字母未出现，用 1 标记其出现。
提示到这里，已经很明显了，可以用一个长 26 的二进制数标记每个字母的出现与否，作为字符串的特征值。
例如，可以这样表示 "adf"：
如何判断两个字符串没有共同字母呢？
两个特征值按位与运算，当且仅当两个位都为 1——也就是这个字母在两个字符串中都出现时——按位与的结果不为 0。
例如，"adf" 与 "ab" 按位与的结果是：
在 'a' 对应的位上为 1，说明有共同字母 'a'。
两个字符串没有共同字母，当且仅当所有位按位与均为 0，也就是特征值按位与等于 0。
进阶优化
位掩码代替数组
一种笨办法是用一个 char[26] 模拟，完成记录后转换成 String 再转换成 int，可以用位掩码简化这一过程。
for (int i = 0; i < len; i++) {
for (char c : words[i].toCharArray()) {
values[i] |= 1 << (c - 'a');
}
}对字符串的每个字符 c，计算其与 'a' 的差值，将 1 左移这个差值位，然后与当前特征值进行按位或，就能将 c 所在的位置 1。
哈希表记录最大长度
对于多个特征值相同的字符串，我们只需要其最大长度，从而减少枚举次数。可以用哈希表记录，key 为特征值，value 为这组字符串的最大长度。
Map<Integer, Integer> maxLen = new HashMap<>();
...
maxLen.merge(value, words[i].length(), Math::max);下文的代码没有给出，读者可自行实现。
复杂度
- 时间复杂度：，其中 为
words[i]的长度之和。 - 空间复杂度：
代码
Java
class Solution {
public int maxProduct(String[] words) {
int len = words.length;
int[] values = new int[len];
// 预处理 words, 计算特征值
for (int i = 0; i < len; i++) {
for (char c : words[i].toCharArray()) {
values[i] |= 1 << (c - 'a');
}
}
// 枚举, 更新答案
int ans = 0;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if ((values[i] & values[j]) == 0) {
ans = Math.max(words[i].length() * words[j].length(), ans);
}
}
}
return ans;
}
}Python
class Solution:
def maxProduct(self, words: List[str]) -> int:
n = len(words)
values = [0] * n
# 预处理 words, 计算特征值
for i in range(n):
for c in words[i]:
values[i] |= 1 << (ord(c) - 97)
# 枚举, 更新答案
ans = 0
for i in range(n - 1):
for j in range(i + 1, n):
if values[i] & values[j] == 0:
ans = max(len(words[i]) * len(words[j]), ans)
return ansC++
class Solution {
public:
int maxProduct(std::vector<std::string>& words) {
int len = words.size();
std::vector<int> values(len, 0);
// 预处理 words, 计算特征值
for (int i = 0; i < len; i++) {
for (char c : words[i]) {
values[i] |= 1 << (c - 'a');
}
}
// 枚举, 更新答案
int ans = 0;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len - 1; j++) {
if ((values[i] & values[j]) == 0) {
int cur = words[i].length() * words[j].length();
ans = std::max(cur, ans);
}
}
}
return ans;
}
};相关题目
187. 重复的DNA序列
266. 回文排列
389. 找不同
最后
更多系列「外源推文」&「生活分享」关注公众号：