最大单词长度乘积 图解题解
这道题到底在问什么
- words
- ["abcw","baz","foo","bar","xtfn","abcdef"]
- 输出
- 16
- 来自
- "abcw"(4) × "xtfn"(4),无公共字母
最优解：一步一步想明白
- 3两两配对本身省不掉(这是 O(n²) 对),真正慢的是每对都要逐字母比「有没有公共字母」。能不能把这步变成一眨眼?
- 4把每个词压成一个整数:第 0 位代表 a、第 1 位代表 b……第 25 位代表 z。词里出现某字母,对应位就置 1。两个词按位与 = 0 就说明没有公共字母——一次运算搞定!
- 5abcw 的 4 个字母,逐个点亮位把单词的字母摊开成一排。先处理 abcw:掩码从 0 开始,扫到一个字母就把它对应的位置 1。
- 6a 是第 0 个字母 → 点亮第 0 位指针落在 a。a 排第 0,就把掩码第 0 位置 1,这格点亮。掩码现在记着 {a}。
- 7b 是第 1 个字母 → 点亮第 1 位指针挪到 b(第 1 个),点亮第 1 位。已点亮的格子累积成 {a, b}。
- 8c 是第 2 个字母 → 点亮第 2 位指针到 c(第 2 个),点亮第 2 位。掩码 {a, b, c}。
- 9w 是第 22 个字母 → 点亮第 22 位最后到 w(第 22 个字母),点亮第 22 位。abcw 扫完,掩码 = {a, b, c, w},四个开关亮着。这个整数就代表了 abcw 用过的所有字母。
- 10每个词一个整数,封存待配同样手法把六个词都压成掩码(foo 有两个 o,但位掩码只管有没有、不管几个,所以是 {f,o})。现在每个词就是一个整数。下面让 abcw 当主角,和后面每个词两两按位与。
- 11AND 不为 0 → 有公共字母固定 abcw(绿),和 baz 按位与,结果留下 {a,b}——不为 0,两词共用了 a、b,不能配。
- 12AND = 0 → 可配!abcw 和 foo 按位与 = 0,没有公共字母,可以配!长度 4 × 3 = 12。best 更新成 12(baz 已比过变灰)。
- 13AND 不为 0 → 跳过abcw 和 bar 共用 a、b,按位与不为 0,跳过。best 还是 12。
- 14AND = 0 → 乘积刷新 16重头戏:abcw 和 xtfn 按位与 = 0!字母完全不沾边,4 × 4 = 16。best 刷新成 16——这就是最终答案。
- 15AND 不为 0 → 跳过abcw 配 abcdef 共用 a、b、c,跳过。abcw 这一轮配对结束,best = 16。
- 16AND = 0 → 3×3=9 < 16abcw 封存变灰,换 baz 当主角。baz 和 foo 能配,但 3×3=9 追不上 16。
- 17AND 不为 0 → 跳过baz 和 bar 共用 a、b,跳过。
- 18AND = 0 → 3×4=12 < 16baz 和 xtfn 能配,但 3×4=12 还是追不过 16。
- 19AND = 0 → 3×3=9 < 16再换 foo 当主角,foo 和 bar 能配,9 < 16。
- 20AND 不为 0 → 跳过(共用 f)foo 和 xtfn 都含 f,按位与留下 {f},跳过。
- 21AND = 0 → 3×4=12 < 16bar × xtfn 能配,12 仍追不过 16。
- 22AND 不为 0 → 跳过(共用 f)最后一对 xtfn × abcdef 都含 f,按位与留下 {f},跳过。所有 15 对都比完了。
- 23最优对: abcw × xtfn ✓所有 15 对都比过一遍,最大乘积来自绿色的 abcw × xtfn,答案 16。位掩码把每对的「逐字母比对」压成了一次按位与。
- 27逻辑反了 → 漏掉正确对假如把条件写反成 != 0 才更新,真正合法的 abcw×xtfn(按位与=0)反而被跳过,答案就错了。按位与为 0 才是「无公共字母 = 可配」。
⚠️ 容易写错的地方
✗ 错：用 set 存每个词的字母,再求交集
✓ 对：用一个 int 的 26 位当掩码
int 按位与是一条 CPU 指令,set 交集要建哈希、慢且费内存
✗ 错：判断写成 masks[i] & masks[j] != 0 才算可配
✓ 对：应是 == 0 才可配(无公共字母)
& 的结果是「公共字母集合」,为 0 才代表不重叠
✗ 错：C/Java 里漏写括号 masks[i] & masks[j] == 0
✓ 对：加括号 (masks[i] & masks[j]) == 0
== 优先级高于 &,不加括号会先算 masks[j]==0,逻辑全错
完整代码（Python / C++ / Java）
Python
class Solution:
def maxProduct(self, words):
n = len(words)
masks = [0] * n
for i, w in enumerate(words):
for ch in w:
masks[i] |= 1 << (ord(ch) - ord('a')) # 点亮对应位
best = 0
for i in range(n):
for j in range(i + 1, n):
if masks[i] & masks[j] == 0: # 无公共字母
best = max(best, len(words[i]) * len(words[j]))
return bestC++
class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
vector<int> masks(n, 0);
for (int i = 0; i < n; i++)
for (char ch : words[i])
masks[i] |= 1 << (ch - 'a'); // 点亮对应位
int best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if ((masks[i] & masks[j]) == 0) // 无公共字母
best = max(best, (int)(words[i].size() * words[j].size()));
return best;
}
};Java
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] masks = new int[n];
for (int i = 0; i < n; i++) {
for (char ch : words[i].toCharArray()) {
masks[i] |= 1 << (ch - 'a'); // 点亮对应位
}
}
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((masks[i] & masks[j]) == 0) { // 无公共字母
best = Math.max(best, words[i].length() * words[j].length());
}
}
}
return best;
}
}复杂度
时间复杂度
O(L + n²)
L 是所有单词总字母数(压掩码一遍);两两配对 n² 对,每对的按位与是 O(1)
空间复杂度
O(n)
只存 n 个整数掩码,每个 4 字节
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大单词长度乘积 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用位掩码而不是 set?+
26 个字母正好塞进一个 int 的低 26 位;按位与判重叠是 O(1) 的单条指令,远快于 set 求交集,且省内存。
配对那步 O(n²) 还能更快吗?+
可用哈希:把相同掩码的词只留最长的(同掩码无法互配),再两两比;最坏仍 O(n²),但去重后实际更快。
如果字母不止 26 个(含大写/数字)怎么办?+
位数不够就用 long(64 位)或 bitset;思路不变,只是掩码的容量变大。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大单词长度乘积 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。