1. 先认识一下 Maximum Product of Word Lengths1.1 题目到底在说什么昨天刷力扣的时候碰到一道题编号 318名字叫 Maximum Product of Word Lengths。题面很短翻译过来就是给你一个字符串数组 words请找出两个单词这两个单词不能含有任何共同字母然后返回它们长度的乘积最大值如果不存在这样的两个单词就返回 0。这里“共同字母”指的是集合意义上的交集不管字母出现几次。举个例子abc和cde有共同字母c就不能配成一对abc和def没有共同字母它们的长度乘积就是 3 × 3 9。力扣官方给了一个示例输入words [abcw,baz,foo,bar,xtfn,abcdef]答案应该是 16。因为abcw长度为 4xtfn长度也为 4这两个单词没有任何共同字母乘积 16是全局最大。其他组合要么有交集要么乘积不如它大。题目给出的约束条件也挺友好单词数量最多 1000 个每个单词长度最多 1000并且只包含小写字母。范围不大但如果不加思考直接暴力最坏情况仍然可能跑到百万级别比较再加上集合判断就有点难受了。这类题目在力扣上属于“中等”难度但它的核心解法非常典型用的是二进制特性来做状态压缩。我第一次看到高票答案时确实有一种“原来还能这样”的感觉。所以这篇题解笔记我想把完整的思考链路、位掩码原理、剪枝算法细节、常见坑位全部拆开讲一遍。不管你是刚开始刷力扣的新手还是已经刷了不少题但遇到位运算就发怵的读者这篇都应该能帮上忙。1.2 这题为什么值得写一篇题解先说结论这题是理解“二进制状态压缩”的一道绝佳入门题。它不像动态规划那样需要复杂的转移方程也不像图论那样需要建图它只需要你明白两件事第一用 32 位整数里的 26 位去表示 26 个字母是否出现第二用按位与来判断两个集合是否有交集。这两件事想清楚一道中等题就变成一道“枚举 位运算”的送分题。很多人第一反应是维护一个HashSetCharacter然后对每对单词做contains判断。这个思路没有错但效率低。每次比较都要遍历集合或者做哈希查询两个单词各走一遍复杂度至少是 O(L1 L2)。而二进制掩码只要一次按位与时间复杂度是 O(1)而且是用 CPU 最底层的电路运算完成的常数极小。除此之外位掩码还天然适合做“两两配对”的枚举只要maskA maskB 0就能确定两个集合不相交。这个直觉一旦建立以后做子集枚举、状态压缩 DP、还有那些“出现次数奇偶”的题目都会顺畅很多。因此我把这道题放在我的“力扣 101 算法题解笔记”系列里作为位运算专题的第一篇。下面按我的实际做题顺序从暴力开始一步步优化到最终版本。2. 二进制特性一个 int 就能装下 26 个字母2.1 状态压缩的直觉来源为什么一看到“只包含小写字母”这个条件就该条件反射地想到二进制位因为小写字母一共 26 个而一个int是 32 位每一位天然可以表示一个“开/关”状态。26 个字母正好塞进 32 位里还多出 6 位空闲。这种用若干个二进制位表示一个状态集合的方法就叫状态压缩。具体怎么映射最简单的约定是让第 0 位表示字母a第 1 位表示字母b第 25 位表示字母z。如果一个单词里出现了字母c我们就把第 2 位变成 1。例如单词abc对应的二进制应该是低位从右往左数第 0、1、2 位都是 1其他位是 0。用十六进制看是0x7用二进制写是0000...000111。字母z单独出现则是第 25 位为 1也就是1 25。这样设计有什么好处直觉上就像两个房间里各挂了一串钥匙钥匙上标着字母。我们要检查两个房间有没有一模一样的钥匙最原始的办法是把两串钥匙分别摊开逐个比对。位掩码则把整串钥匙浓缩成一个数字然后只需要一次“按位与”操作如果结果不是 0说明至少有一把钥匙同时出现在两个房间里如果结果是 0说明两串钥匙没有任何交集。CPU 对“与”运算的吞吐量远高于循环遍历所以这种做法的优势在小数据上可能不明显但在 1000 个单词的两两比较中会非常直观。2.2 掩码的构造与判断构造一个单词的掩码非常简单。遍历单词里的每个字符ch计算它相对于a的偏移量idx ord(ch) - ord(a)然后用mask | 1 idx把对应位置 1。这里有一个细节同一个字母出现多次不需要特殊处理因为按位或运算触发了幂等性1 | 1还是 1。所以aba和ab会得到完全相同的掩码只关心“有没有”这个字母不关心出现次数。判断两个单词是否含有共同字母只需要一行if maskA maskB 0: # 没有任何共同字母注意 Python 的运算符优先级里的优先级低于。如果直接写成maskA maskB 0Python 会先计算(maskA maskB) 0这其实刚好是我们想要的结果所以写成这样也没问题。但为了可读性我建议显式加括号(maskA maskB) 0。在 C 或 Java 里的优先级低于所以如果你写maskA maskB 0会先算maskB 0再算maskA ...那就会出大问题。这是一个非常经典的细节后面我会再强调。2.3 为什么位运算比 Set 更合适用集合也能完成判定比如set(words[i]) set(words[j])但它需要先创建两个set然后做交集或遍历。如果你的解法在双层循环内部才去建集合那复杂度会退化得非常难看。正确的做法是提前把每个单词都转换成一个不可变的结构然后比较起来才快。而位掩码本身就是不可变整数既可以直接存数组也可以作为字典的 key甚至不需要考虑哈希碰撞问题。更重要的是位掩码不只是一个存储容器。它还能参与计算比如你想知道某个单词的掩码是否是另一个掩码的子集可以用(a b) a判断想统计一个集合里有多少个 1可以用bin(mask).count(1)或者内置的int.bit_count()想枚举某个掩码的所有非空子集可以用sub (sub - 1) mask。这些操作在纯Set结构下都很别扭但在整数上只需要一行位运算。这也是为什么二进制特性在算法竞赛和力扣中等难度以上的题目里频繁出现的原因。3. 暴力枚举 位掩码第一版能 AC 的解法3.1 完整思路和代码先给出最容易理解的第一版解法。步骤很简单遍历所有单词为每个单词生成一个掩码存到数组masks里。双层循环枚举所有下标对(i, j)要求i j避免重复。如果(masks[i] masks[j]) 0说明两个单词没有共同字母更新答案ans max(ans, len(words[i]) * len(words[j]))。如果所有组合都不满足循环结束后ans保持 0直接返回。代码实现如下class Solution: def maxProduct(self, words: List[str]) - int: n len(words) masks [0] * n for i, w in enumerate(words): mask 0 for ch in w: mask | 1 (ord(ch) - ord(a)) masks[i] mask ans 0 for i in range(n): for j in range(i 1, n): if (masks[i] masks[j]) 0: ans max(ans, len(words[i]) * len(words[j])) return ans这段代码的时间复杂度是 O(N² totalLength)。其中totalLength是所有单词长度之和用来生成掩码双层循环的 N² 次位运算每对组合只做一次常数时间的按位与。空间复杂度 O(N)用来存储掩码。3.2 复杂度和运行表现N 最大是 1000N² 就是 100 万。100 万次int运算在现代电脑上大概几毫秒级别。再加上字符串长度总计最多 100 万总操作量也就两百万级别。所以这个“暴力”版本不需要任何花哨优化在力扣上已经能轻松通过。很多人一听到“暴力”两个字就下意识皱眉其实暴力枚举在这里并不可怕因为数据范围限制摆在那里N1000 是特意设计成允许 O(N²) 的。真正 O(N²) 会超时的场景通常是 N 达到 1e5 甚至 1e6那时候才必须优化。不过这个版本有一个小缺点内层循环对所有单词对都执行即使已经找到很大答案也不会提前停。比如你已经找到一个长度乘积是 400 的组合后面依然会把剩下几十万对全部比完。这不影响正确性但不够“聪明”。既然标题里提到了剪枝算法我们自然会想能不能利用“要求乘积最大”这个目标让循环提前结束答案是可以而且实现非常简单第四部分会详细说。3.3 写代码最容易踩的两个坑第一个坑是运算符优先级。刚才提过C 和 Java 中优先级低于所以不要写if (maskA maskB 0)。正确写法是if ((maskA maskB) 0)。Python 在解析这行时恰好等价于加括号但为了跨语言习惯一致建议一律加上括号。这是不少人在白板面试时容易犯的隐蔽错误。第二个坑是答案初始值。ans一定要初始化为 0而不是一个很大的数。因为如果所有单词两两之间都有公共字母函数必须返回 0。初始化为 0 还有一个好处max更新时不会把 0 误算成有效答案。再看空字符串的情况如果words里有空字符串它的掩码是 00 任何掩码 0所以它和任何单词都能配对但长度是 0乘积是 0不会更新答案。这个性质不会破坏正确性但一开始想明白会少一些困惑。4. 进阶优化剪枝算法和掩码去重4.1 按长度降序乘积不可能再大就剪掉很多求“最大值”的枚举题都可以用“先排序再剪枝”的思路来加速。这道题也一样先把单词按长度从长到短排序然后外层循环从最长的单词开始选内层循环也从剩下的较长单词开始选。一旦发现当前两个单词的长度的乘积已经小于等于ans那么后面的单词只会更短乘积只会更小此时就可以直接break掉内层循环。为什么可以这样剪因为我们已经按长度降序处理。假设外层固定了一个长度len_i内层从第i1个单词开始遍历内层单词的长度是非递增的。当遍历到第j个单词时如果len_i * len_j ans那么对于所有k j都有len_k len_j所以len_i * len_k len_i * len_j ans。后续组合不可能刷新答案继续枚举没有意义直接中断内层循环即可。更进一步如果当前外层单词自身长度的平方都小于等于ans那它和任何单词的乘积都不可能超过ans整个外层循环都可以提前结束。这个剪枝对“已经有较大答案”的场景效果格外明显。举个例子假设有一堆长度为 1000 的单词你很快找到了两个不重叠单词乘积是 1000000那么外层剩下那些长度不足 1000 的单词都不用再看了。4.2 相同掩码只留最长单词正确性证明第二个优化是如果多个单词的掩码完全相同只保留其中长度最大的那个其余可以全部丢掉。为什么因为掩码相同意味着这些单词包含的字母集合完全一样。对于任意一个第三方单词w它和掩码 X 的单词是否有交集只取决于掩码 X与具体单词内容是哪个无关。既然交集关系相同我们在比较时只需要比较“掩码 长度”。相同掩码下长度最大的单词一定比其他单词更能产生大的乘积所以其他单词是严格劣势的不可能出现在最优解里。这个去重操作可以把 N 个单词压缩成最多 2^26 种掩码但实际单词数量只有 1000所以压缩后只少不多。如果题目出现大量同字母单词比如[a, aa, aaa, b, bb]去重后就只剩掩码{a}长度 3 和掩码{b}长度 2两个掩码一配对答案就是 6。如果不做去重暴力比较 5 个单词也能算出同样答案但做了去重后代码更简洁剪枝效果也更好。在具体实现上可以选择用哈希表dict记录每个掩码对应的最大长度。遍历所有单词计算出掩码后更新dict[mask] max(dict.get(mask, 0), len(w))。最后把字典的键值对转成(length, mask)列表再对这个列表按长度降序排序。这样既去重又为剪枝做好了准备。4.3 把两个优化合起来的最终版本把排序剪枝和掩码去重组合起来就得到一份更漂亮的解法class Solution: def maxProduct(self, words: List[str]) - int: mask_to_len {} for w in words: mask 0 for ch in w: mask | 1 (ord(ch) - ord(a)) if len(w) mask_to_len.get(mask, 0): mask_to_len[mask] len(w) items sorted( [(length, mask) for mask, length in mask_to_len.items()], reverseTrue ) ans 0 m len(items) for i in range(m): len_i, mask_i items[i] if len_i * len_i ans: break for j in range(i 1, m): len_j, mask_j items[j] if len_i * len_j ans: break if (mask_i mask_j) 0: ans len_i * len_j return ans这里有三个容易忽视的细节。第一去重后的掩码之间可能也存在“掩码包含另一个掩码”的情况比如掩码集合{a,b}和{a}必然有交集判断时用按位与自动排除不需要额外处理。第二items按(length, mask)整体降序而 Python 的元组比较会先按长度排所以可以保证len从大到小。第三外层剪枝条件写成len_i * len_i ans是为了安全触发提前结束如果当前最长单词平方都不超过答案那么任何两两组合都不可能超过答案虽然理论上最小的配对组合是两个不同的单词最坏也就等于平方所以这个条件是充分且安全的。这份优化代码在最坏情况下复杂度依然是 O(U²)其中 U 是去重后的掩码数量U min(N, 2^26)。由于 N 1000U 也不可能超过 1000所以整体依然是 O(N²) 量级。但剪枝在实际测试中通常会大幅减少比较次数尤其是当存在一个很大的可行答案时外层循环往往跑不到几个单词就结束了。5. 8 组测试用例帮你彻底理解5.1 用例与期望输出为了验证自己的实现建议把下面这些用例都跑一遍。它们覆盖了普通情况、空字符串、同字母重复、全冲突、长字符串等常见场景。输入 words期望输出说明[abcw,baz,foo,bar,xtfn,abcdef]16力扣官方示例[a,ab,abc,d,cd,bcd,abcd]4ab和cd无交集2×24[a,aa,aaa,b,bb]6最长 a 串和最长 b 串3×26[a,b,c]2任意两个单字母都不重复[a,b,a,b]1去重后只剩两个掩码长度都是 1[aaa,aaa]0两个单词都含字母 a[, abc]0空串掩码为 0但乘积为 0[a * 1000, b * 1000]1000000最大化边界测试剪枝效果5.2 手工推演其中两组第一组[a,ab,abc,d,cd,bcd,abcd]。我们逐一看掩码。a的掩码只有 a 位ab有 a、babc有 a、b、cd只有 d 位cd有 c、dbcd有 b、c、dabcd全占。容易发现ab长度2和cd长度2没有交集乘积 4。还有没有更大的abc和任意含 d 的字符串都有交集 c 或 d不能配abcd和谁都交集。所以答案就是 4。这个用例很适合验证去重逻辑比如a、aa如果出现都只保留最长。第二组[a,aa,aaa,b,bb]。如果不做去重长度数组是 1、2、3、1、2。枚举时aaa和bb无交集乘积 6这是最大的。因为 a 串之间都有交集b 串之间也有交集跨 a/b 的组合里长度最长的就是 3×26。如果只按暴力法会比较 C(5,2)10 对用去重后只剩{a: 3, b: 2}一次比较直接得到答案代码更少思路更清楚。5.3 边界场景总结边界情况最容易出问题的是空字符串和重复单词。空字符串的掩码为 00 与任何整数按位与都为 0所以它总能和别人类似地配对但乘积为 0对最终答案没有影响除非整个数组只有空串和另一个空串那也是 0。这个行为是符合题意的题目要求“长度乘积”空串长度为 0自然返回 0。另一个边界是words数量为 2 且它们有共同字母此时双层循环只有一次比较按位与非 0ans保持 0返回 0。如果它们没有共同字母则返回两个长度的乘积。这样的边界小用例用来自测非常方便。还有一点题目固定只有小写字母所以ord(ch) - ord(a)的范围是 0 到 25绝不会超过 31用int存储不会溢出。如果把题目改成 ASCII 全集就不能再这么玩了需要换用更长的整数或者bitset。所以在刷题时看到“小写字母”这个条件一定要立刻联想到位掩码。6. 从这题延伸出去位运算/状态压缩还有哪些玩法6.1 怎么一眼识别“位掩码题”经历了这道题之后我总结了几个提示信号只要题目命中其中两个以上就可以优先考虑用二进制状态压缩数据范围里出现“只含有小写字母”“元素种类很少如不超过 32”“每个元素的状态只有取/不取两种”。题目需要判断两个集合是否有交集、是否互为子集、是否完全相同。题目要求枚举所有子集或者用某个整数表示一种“特征组合”。题目与“出现奇偶次数”相关因为异或天然适合统计奇偶。当然位掩码并不是万能的。如果状态太多一个int存不下就要考虑bitset或者long long再不行就得换思路。但在力扣的中等题里只要数据维度不超过 32位掩码往往是最高效的解法之一。6.2 值得一起刷的几道力扣题学完这道题我建议顺手把下面几道一起刷掉它们刚好能把位运算的几个常用方向串起来LeetCode 78 子集可以用枚举掩码遍历所有子集是“二进制状态压缩”最直观的入门题。LeetCode 137 只出现一次的数字 II利用位运算逐位统计出现次数模 3 的结果考察位运算的进阶理解。LeetCode 260 只出现一次的数字 III利用异或和分组技巧找出两个只出现一次的数字。LeetCode 477 汉明距离总和每个 bit 独立统计 0 和 1 的数量最后求和。LeetCode 898 子数组按位或操作虽然难度稍高但同样和位运算的单调性有关。这几道题如果都能独立写出来你对位运算的掌控力会明显上一个台阶。以后再遇到状态压缩 DP比如“旅行商问题”的经典状态dp[mask][i]接受起来也会容易很多。6.3 我的个人心得就 Maximum Product of Word Lengths 这一题而言我最想强调的一个心得是暴力解法并不可耻关键是暴力之前先想清楚“用什么数据结构来表达比较的单位”。从Set到int表面的变化只是内存优化实质的变化是让比较操作从“遍历”变成了“CPU 指令”。这种思维转变比记住某个具体公式重要得多。另外剪枝代码里的break条件要配合排序前提去理解否则容易写错。我自己第一次写的时候曾经忘了先按长度排序直接套用break结果答案低估。所以这类“为保证正确性而必须先排序再剪枝”的模式建议在代码注释里写明前提避免以后回看时一脸茫然。最后再分享一个小技巧如果你在面试中遇到这道题可以先从暴力位掩码讲起让面试官看到你能快速给出 AC 版本然后再主动提“相同掩码只留最长”和“按长度排序剪枝”这两个优化。这种递进式的答题节奏比一上来直接甩出最优解更能体现思路清晰度也更容易留下好印象。算法题的价值从来不只是“ AC 那一瞬间”而是你把一个看似复杂的问题拆解成简单、可证明、可优化的过程。这道题做到了希望你也能从这篇笔记里拿到同样的启发。