LeetCode LCR 005. 最大单词长度乘积
目录
题目描述
题意分析
给一个只含小写字母的字符串数组
words，从中挑两个不含任何公共字母的单词，返回它们长度乘积的最大值；如果不存在这样的两个单词，返回 $0$。要求的是「最大乘积」，而乘积只由两个单词的长度决定，所以真正需要快速回答的问题只有一个：给定两个单词，它们有没有公共字母。单词内部字母的顺序、重复次数全都无关紧要，只有「出现过哪些字母」这个集合信息有用。
关键约束是字符集只有 26 个小写字母。一个 26 元素的集合，正好能塞进一个
int的低 26 位；两个集合是否相交，就退化成一次按位与是否为零。这条约束是把「逐字符比较」压成「一次机器指令」的全部依据。数据规模上，
words的长度是 $10^3$ 级，单词总长在 $10^3 \sim 10^4$ 量级。两两枚举是 $10^6$ 级，完全可以接受；真正不能接受的是在每一对内部再逐字符比较，那会把总代价推到 $10^9$ 以上。边界方面：不存在合法配对时返回 $0$，因此答案变量初始化为 $0$ 就天然覆盖了这种情况；数组里可能有重复单词，但重复单词彼此必然有公共字母（除非是空串，题目不保证出现），会被判定条件自动排除，不需要去重。
解法：位运算压缩状态
核心思路
暴力做法是枚举所有单词对，对每一对做一次「是否有公共字母」的判断，判断方式是把其中一个单词的字母塞进集合再逐个查另一个。设 $n$ 是单词数、$L$ 是单词平均长度，代价是 $O(n^2 L)$。瓶颈非常清楚：同一个单词的字母集合被反复重建了 $O(n)$ 次。
观察点是：单词的字母集合在整个过程中根本不会变，完全可以预处理一次、复用 $O(n)$ 次。而既然字符集只有 26 个字母，这个集合不需要用
HashSet或长度 26 的布尔数组来存——用一个整数的第 $0$ 到第 $25$ 位表示'a'到'z'是否出现即可。于是要维护的状态是：
mask[i]的第 $k$ 位为 $1$，当且仅当words[i]中出现过字母'a' + k。有了这个表示，「两个单词无公共字母」这个判定就等价于mask[i] & mask[j] == 0——按位与的每一位都在同时检查一个字母，一条指令顶 26 次比较。整体流程变成两段：第一段扫一遍所有单词建
mask，代价 $O(\sum L)$；第二段两两枚举，每对只做一次按位与和一次乘法，代价 $O(n^2)$。答案变量从 $0$ 起步，遇到合法对就取较大者，天然处理了「无解返回 $0$」。
解题步骤
- 先建掩码表：对每个单词，遍历它的字符，执行
mask[i] |= 1 << (c - 'a')。用「或」而不是「加」，是因为同一个字母出现多次时「或」是幂等的，而「加」会进位串到相邻字母上，把集合信息彻底破坏。c - 'a'把字母映射到 $0 \sim 25$ 的位下标。题目保证全是小写字母，所以不需要额外的合法性判断。- 建表必须独立于配对循环，这正是从 $O(n^2 L)$ 降到 $O(n^2 + \sum L)$ 的那一步——同一个单词的集合只算一次。
- 配对时内层从
j = i + 1起。乘法可交换，(i, j)与(j, i)结果相同，从i + 1起可以省掉一半枚举，同时天然排除了i == j的自配对。- 判定条件写
(mask[i] & mask[j]) == 0。Java 里&的优先级低于==，括号不能省，否则表达式会被解析成mask[i] & (mask[j] == 0)而编译失败或语义错乱。- 只在判定通过时更新答案：
answer = max(answer, len_i * len_j)。乘法只在无公共字母时才有意义，把它放在条件内部既是语义要求也省去无谓计算。- 答案初始化为 $0$，循环结束直接返回，无解情形不需要任何特判。
以
words = ["ab", "cd", "abc"]走一遍。建表阶段："ab"用到a、b，mask[0] = 0b000011 = 3；"cd"用到c、d，mask[1] = 0b001100 = 12；"abc"用到a、b、c，mask[2] = 0b000111 = 7。配对阶段：(0, 1)的3 & 12 = 0，无公共字母，乘积 $2 \times 2 = 4$，answer = 4；(0, 2)的3 & 7 = 3 ≠ 0，公共字母是a、b，跳过；(1, 2)的12 & 7 = 4 ≠ 0，公共字母是c，跳过。返回4。注意(1, 2)那次按位与的结果4 = 0b100恰好指出了冲突发生在第 $2$ 位即字母c上——这就是位表示相对布尔数组的额外好处：结果本身携带了「哪些字母冲突」的完整信息。
代码实现
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] mask = new int[n];
// 预处理：每个单词的字母集合压进一个 int 的低 26 位，只算一次。
for (int i = 0; i < n; ++i) {
for (char c : words[i].toCharArray()) {
mask[i] |= 1 << (c - 'a');
}
}
int answer = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
// 按位与为 0 等价于两个字母集合不相交。
if ((mask[i] & mask[j]) == 0) {
answer = Math.max(answer, words[i].length() * words[j].length());
}
}
}
return answer;
}
}
func maxProduct(words []string) (answer int) {
n := len(words)
mask := make([]int, n)
// 预处理：每个单词的字母集合压进一个整数的低 26 位，只算一次。
for i, w := range words {
for _, c := range w {
mask[i] |= 1 << (c - 'a')
}
}
for i, x := range mask {
for j := i + 1; j < n; j++ {
// 按位与为 0 等价于两个字母集合不相交。
if x&mask[j] == 0 {
answer = max(answer, len(words[i])*len(words[j]))
}
}
}
return
}
复杂度分析
- 时间复杂度：$O(n^2 + \sum L)$，其中 $n$ 是单词数、$\sum L$ 是所有单词的总长度。建表阶段每个字符只被访问一次；配对阶段每对只做一次按位与与一次乘法，是常数操作。凭的是「集合预处理」把内层的逐字符比较彻底消掉了。
- 空间复杂度：$O(n)$，只额外开了长度为 $n$ 的掩码数组。每个集合被压成一个 32 位整数，相比每个单词一个
HashSet或长度 26 的数组，常数小了一到两个数量级。
关键点总结
- 字符集有限（26 个小写字母、10 个数字、ASCII 128）时，集合就该用整数的二进制位表示：判交是一次
&、判包含是a & b == b、求并是|，全都是常数时间且缓存友好。- 「同一个对象在双层循环里被反复重算」是最常见的可优化点，把不变量提到循环外预处理，往往能直接砍掉一个维度。
- 用「或」而不是「加」来置位，是位集合的铁律；「加」在字母重复时会进位污染相邻位。
- 答案变量的初值要与「无解时的返回值」对齐，本题恰好都是 $0$，于是不需要任何无解特判——这是初值选择带来的免费收益。
- 面试视角：面试官抛出这题时，$O(n^2 L)$ 的暴力必须能秒写出来当保底，然后主动指出「字母集合可以压成 int」的优化点。被追问「$n$ 再大怎么办」时，正确回答是：可以按掩码去重（相同掩码只保留最长的那个单词），把 $n$ 上界压到 $2^{26}$ 与去重后的规模，或者枚举每个掩码的补集的子集，但那些做法在本题数据范围下并不划算——能说清「什么时候不该继续优化」同样是加分项。
易错点总结
- 错误写法：
mask[i] += 1 << (c - 'a')。输入["aa", "b"]时"aa"的掩码变成 $2$（进位到了字母b的位），与"b"的掩码相交，返回0而不是2。- 错误写法：把建掩码的循环写进配对的双层循环里。结果正确但复杂度回到 $O(n^2 L)$，在 $n = 1000$、单词长 $1000$ 的数据上必然超时。
- 错误写法：Java 里写成
if (mask[i] & mask[j] == 0)。==的优先级高于&，表达式被解析成mask[i] & (mask[j] == 0)，直接编译报错；括号是必需的。- 错误写法：判定写成
(mask[i] | mask[j]) == 0。「或」判的是「两个都是空集」而不是「不相交」，输入["ab", "cd"]时3 | 12 = 15 ≠ 0，返回0而不是4。- 错误写法：位移写成
1 << c而不是1 << (c - 'a')。'a'的码值是 $97$，Go 里1 << 97已经移出 64 位范围变成 $0$，所有掩码都是 $0$，输入["ab", "abc"]会被误判为不相交并返回6。- 错误写法：用
Math.max时把乘积写成words[i].length() * words[j].length()之外的长度来源，比如误用mask的位数。位数只反映不同字母的个数，"aab"的位数是 $2$ 而长度是 $3$，输入["aab", "cc"]会返回4而不是6。- 错误写法：答案变量初始化成
Integer.MIN_VALUE或-1。输入["a", "a"]不存在合法配对，循环一次都不更新，返回的是那个哨兵值而不是题目要求的0。- 错误写法：用
HashSet<Character>存集合再调retainAll判交。逻辑对，但每次判交都是 $O(26)$ 且带装箱开销，$10^6$ 对下常数放大几十倍，容易卡在时限上。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 318. 最大单词长度乘积 | 中等 | 与本题同题，可直接套用同一份掩码 + 两两枚举 |
| 1239. 串联字符串的最大长度 | 中等 | 从「选两个」升级为「选任意多个」，需回溯或子集 dp 维护累积掩码 |
| 1178. 猜字谜 | 困难 | 判定从「不相交」变成「是子集且含首字母」，要枚举掩码的子集 |
| 78. 子集 | 中等 | 用 $2^n$ 个整数枚举全部子集，是位表示集合的最基础形态 |
| 136. 只出现一次的数字 | 简单 | 同样是位运算，但用的是异或的自消性质而非位集合 |