力扣上有一类题读完题干你会觉得“这有什么难的”真上手才发现复杂度像一把钝刀慢慢磨你。Maximum Product of Word Lengths 就是非常典型的一道。这道题在力扣LeetCode里编号 318属于中等难度表面看是字符串处理实际考的是二进制特性把一个单词的字母存在性压缩成一个整数掩码然后一次按位与就能判断两个单词有没有共同字母。我最近把这道题翻出来重新刷了一遍顺手整理出三种常见写法以及一堆藏在细节里的坑。这篇笔记既是给自己留档也是给还在力扣热题里转悠的朋友们一份可以直接抄作业的参考。这道题的英文名起得很直白找出两个没有公共字母的单词让它们长度乘积最大。听起来不难可当你面对几百上千个单词时就得认真想想怎么在 O(n²) 的配对基础上把效率提上去以及怎么避免在优化过程中偷偷丢掉正确答案。读完这篇你应该能理解为什么位掩码是这类题的标配思路也能搞清楚排序剪枝和去重背后那些容易翻车的小逻辑。1. 题目拆解先搞清楚要计算的到底是什么1.1 题干速读与三个容易被忽略的点题目给一个字符串数组words要求返回length(words[i]) * length(words[j])的最大值条件是两个单词“不含共同字母”。如果不存在这样的两个单词就返回 0。这里有三个容易理解偏的地方值得单独拎出来说。第一“不含共同字母”指的是两个单词的字母集合没有交集不是字符计数不同。举个例子abc和def没有共同字母完全合规abc和abd虽然都含 a 和 b但多一个字母、少一个字母都不行——只要共同出现过一个字母就算违规。所以题目本质是在做集合层面的不相交判断而不是字符串比较。第二目标是长度乘积不是字母种类乘积也不是其他什么指标。这意味着句子越长越值钱两个长单词如果可以配对收益远大于两个短单词。到这里你已经能感受到优化方向应该围绕“优先讨好长单词”来展开后面要讲的排序剪枝思路正是从这里长出来的。第三题目只要最大值不要具体是哪两个单词。所以我们全程不需要记录下标只需要维护一个当前最优值ans不断尝试用新配对的乘积去更新它即可。一个直观的例子words [abcw,baz,foo,bar,xtfn,abcdef]。其中abcw和xtfn没有共同字母长度是 4 × 4 16abcw和baz虽然长度乘积也是 4 × 3但共同拥有 a直接出局。最终答案就是 16。1.2 为什么 O(n²) 逃不掉但能偷懒最原始的思路是两层循环枚举所有下标对(i, j)对每一对再逐个字符检查两个单词是否共享字母。数组长度 n 平均是几百上千单词长度 L 最长也能到 1000于是总开销是 O(n² × L)。最坏情况下比如 1000 个单词、每个单词 1000 个字符就有约 10 亿次字符操作跑到超时几乎是板上钉钉的事。但请注意一个关键事实配对检查这一层理想情况下必须巡检所有候选对——因为你无法预测哪一对会给出最大乘积除非已经把它们全部看过一遍。也就是说O(n²) 这个数量级对这类“找全局两两关系最大值”的问题来说基本是绕不开的下界。真正能优化的点有两个把单次检查的成本从 O(L) 压到 O(1)。这正是位掩码的用武之地。通过排序和剪枝让实际执行的对数明显少于 n²平均情况大幅提速虽然最坏情况仍然是 O(n²)。所以整道题的解题路线其实非常清晰先用二进制特性把字符串变成整数再想办法让枚举过程更聪明一点。接下来我们一步一步看。2. 二进制特性把单词压缩成 26 位掩码2.1 用 int 的 26 个位给字母“盖章”为什么一说起“去重判断”就想到位运算因为小写英文字母只有 26 个而一个int在 Java 里是 32 位在 Python 里虽然整数无限大但我们只关心低 26 位也完全够用。于是可以建立一张固定映射字母a对应第 0 位字母b对应第 1 位字母c对应第 2 位...字母z对应第 25 位单词里出现某个字母就把对应位置 1没出现就保持 0。这样每个单词都会被转换成一个非负整数我习惯叫它“掩码”或“签名”。比如abc就会变成二进制最低三位全是 1也就是数字 7abd是 0b1011也就是第三位和最低两位是 1。构造过程用位运算写核心就是两行int mask 0; for (char c : word.toCharArray()) { mask | 1 (c - a); }拆开看是三件事1 (c - a)让数字 1 左移若干位产生一个“只在某一位上是 1”的整数|是做按位或|等于把当前所有已标记的位和新位合并。每遍历到一个字母就把白板上对应的那一格点亮。重复字母不影响结果因为按位或天然具有幂等性。这里可以打一个生活化比方掩码就像一张 26 格的白板卡出现过的字母对应的格子被贴上标签。判断两个单词是否共用字母等价于把两张白板卡叠在一起看看有没有重叠的标签。而位与运算做的正是这件事。2.2 掩码和长度必须分开记录拿到掩码之后马上会遇到一个容易忽略的问题掩码只是“字母存在性”的编码它并不携带字符串的真实长度信息。所以在预处理阶段我习惯用两个平行结构分别保存int[] masks new int[n]; int[] lens new int[n];或者用二元组打包Java 里可以写成int[n][2]Python 里就是list[tuple]。无论哪种原则只有一个掩码和长度必须同步保存、永不分离。为什么这么强调因为aabb和ab的掩码完全一样都只有最低两位是 1数值为 3但真实长度分别是 4 和 2。如果后面只拿着掩码去和别人比较算最终乘积时却用“掩码里的 1 的个数”当长度那就彻底跑偏了。Integer.bitCount(mask)只能告诉你这个单词里有几种不同字母而不是字符串有几个字符。这一点我在后面第 4 节还会再拎出来当反面教材。2.3 一次按位与完成集合交集判断掩码建好后判断两个单词是否共享字母就只剩一条代码if ((masks[i] masks[j]) 0) { // 无共同字母 } else { // 有共同字母跳过 }按位与的规则是“同一位都为 1 结果才为 1”。两个掩码如果在任何一位上同时为 1说明这两个单词都拥有那个字母结果那一位置 1整个整数不为 0。反之结果为零则代表没有任何一位同时为 1两词自然没有共同字母。这个转化的威力在于我们把“字母集合交集是否为空”直接变成“两个整数按位与是否为零”。判断不再依赖字符串长度也不再依赖字母顺序时间复杂度从 O(L) 降到 O(1)。预处理阶段虽然花掉一次 O(总字符数) 的代价去建掩码但之后每次配对判断都是 CPU 级常数操作。整道题的总复杂度就从 O(n²L) 好看地降到了 O(n² 总字符数)。这也是标题里“二进制特性”这四个字的分量所在。3. 三个版本的实现与演进3.1 第一版最朴素的位掩码二重循环先给出最容易理解、也最容易验证正确性的版本。它不做任何排序和剪枝纯粹靠位运算把配对检查变成 O(1)。Java 写法class Solution { public int maxProduct(String[] words) { int n words.length; int[] masks new int[n]; int[] lens new int[n]; for (int i 0; i n; i) { int mask 0; for (char c : words[i].toCharArray()) { mask | 1 (c - a); } masks[i] mask; lens[i] words[i].length(); } int ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { if ((masks[i] masks[j]) 0) { ans Math.max(ans, lens[i] * lens[j]); } } } return ans; } }Python 版本长得差不多class Solution: def maxProduct(self, words: List[str]) - int: masks [] lens [] for w in words: mask 0 for ch in w: mask | 1 (ord(ch) - 97) masks.append(mask) lens.append(len(w)) ans 0 n len(words) for i in range(n): for j in range(i 1, n): if (masks[i] masks[j]) 0: ans max(ans, lens[i] * lens[j]) return ans这一版的思路一句话就能概括先预处理再二重循环见缝插针地更新最大乘积。实测跑力扣50 万次配对对 n1000 来说是 10 的 6 次方量级每次配对只有一条位运算整体毫秒级完成其实已经能通过绝大多数测试数据。很多标答比这版多做的其实是让平均情况更快而不是推翻这套框架。3.2 第二版按长度降序加剪枝第一版的问题在于它把每对都平等看待。可是题目要的是最大乘积而且内层循环里的lens[i] * lens[j]明显受长度影响长度越大的配对越有机会打破当前最优。反过来说一旦某个配对就算乘积再大也比不过手里已有的ans那后面的全部配对就都没必要看了。于是第二版的做法是先把所有单词按长度从大到小排序再套上二重循环。这里需要保证排序的原子性也就是长度和掩码必须作为一个整体跟着动不能用两个独立数组去排。我习惯用二维数组或元组class Solution { public int maxProduct(String[] words) { int n words.length; int[][] items new int[n][2]; // items[i][0] len, items[i][1] mask for (int i 0; i n; i) { int mask 0; for (char c : words[i].toCharArray()) { mask | 1 (c - a); } items[i][0] words[i].length(); items[i][1] mask; } Arrays.sort(items, (a, b) - b[0] - a[0]); int ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { if (items[i][0] * items[j][0] ans) { break; } if ((items[i][1] items[j][1]) 0) { ans items[i][0] * items[j][0]; } } } return ans; } }Pythonclass Solution: def maxProduct(self, words: List[str]) - int: items [] for w in words: mask 0 for ch in w: mask | 1 (ord(ch) - 97) items.append((len(w), mask)) items.sort(keylambda x: -x[0]) # 只按长度降序 ans 0 n len(items) for i in range(n): for j in range(i 1, n): len1, mask1 items[i] len2, mask2 items[j] if len1 * len2 ans: break if (mask1 mask2) 0: ans max(ans, len1 * len2) return ans这段代码里最关键的是break的条件。因为外层单词长度从大到小内层单词长度也是从大到小所以对于固定的i随着j往右移动len2只降不升len1 * len2也一定单调递减。一旦某个len1 * len2不大于ans后面所有j的乘积只会更小继续枚举纯属浪费。这就是剪枝的数学依据。这个版本的正确性完全建立在“长度降序”这个前提上。如果排序时只排了长度没有连带掩码一起交换那内层循环遇到的长度序列不再是降序break就会把潜在的正确答案也一起剪掉。这种错误非常隐蔽我在初学时踩过一次后面第 4 节会专门展开。3.3 第三版相同掩码只保留最长单词继续观察你还能发现一个更聪明的压缩点如果两个单词的掩码完全相同说明它们的字母集合一模一样。对于外部任意一个单词来说这两个单词要么都能配对要么都不能配对因为判断条件只看掩码这位“身份证”。既然它们在所有配对场景下都是同一个命运那我只需要留下其中长度更长的那一个因为最后算乘积时长度更大的那个一定带来更大的数值。具体做法是用一张哈希表掩码 - 该掩码对应的最大长度。遍历所有单词算出掩码后不断更新这张表。class Solution { public int maxProduct(String[] words) { MapInteger, Integer map new HashMap(); for (String w : words) { int mask 0; for (char c : w.toCharArray()) { mask | 1 (c - a); } map.merge(mask, w.length(), Math::max); } Listint[] items new ArrayList(); for (Map.EntryInteger, Integer e : map.entrySet()) { items.add(new int[]{e.getValue(), e.getKey()}); // {最大长度, 掩码} } items.sort((a, b) - b[0] - a[0]); int ans 0; int m items.size(); for (int i 0; i m; i) { for (int j i 1; j m; j) { if (items.get(i)[0] * items.get(j)[0] ans) { break; } if ((items.get(i)[1] items.get(j)[1]) 0) { ans items.get(i)[0] * items.get(j)[0]; } } } return ans; } }Pythonclass Solution: def maxProduct(self, words: List[str]) - int: best {} for w in words: mask 0 for ch in w: mask | 1 (ord(ch) - 97) best[mask] max(best.get(mask, 0), len(w)) items sorted(best.items(), keylambda kv: -kv[1]) # (mask, maxLen)按 maxLen 降序 ans 0 m len(items) for i in range(m): mask1, len1 items[i] for j in range(i 1, m): mask2, len2 items[j] if len1 * len2 ans: break if (mask1 mask2) 0: ans max(ans, len1 * len2) return ans这里有个非常隐蔽但必须强调的细节去重后如果你直接用map.entrySet()的遍历顺序去套用第二版的break剪枝会出错。因为HashMap的迭代顺序和长度大小没有任何关系内层循环的乘积不是单调递减的此时break就等于漏答案。正确做法是先把map里的条目按“最大长度”降序排序再进入双层循环。第三版代码里我特意先排序再循环就是吸取了这个教训。当然如果你不想排序也可以那就老老实实跑 O(m²) 的全量枚举其中 m 是去重后掩码数量。大多数情况下 m 远小于原始 n所以即使不剪枝性能也够看。3.4 复杂度对比与正确性论证把三版放在一起看方案预处理复杂度配对次数单次配对成本核心代价朴素位掩码O(总字符数)O(n²)O(1)代码最简单排序剪枝O(总字符数 n log n)平均远小于 n²最坏 O(n²)O(1)需要理解单调性掩码去重O(总字符数 m log m)O(m²)m ≤ nO(1)需要小心迭代顺序其中总字符数就是所有字符串长度之和一般远小于 n²可以忽略。三版的正确性都建立在一个共同逻辑链上掩码构造的正确性第 i 位是否为 1等价于字符串是否包含字母ai由构造过程逐位保证配对判断的正确性两掩码按位与为 0当且仅当不存在某一位同时为 1当且仅当不存在共同字母排序剪枝的正确性外层固定的情况下内层乘积单调不增一旦不大于当前最优值后面不可能更好去重的正确性相同掩码的外部可配对性完全相同只保留最长长度不会漏掉更大的乘积。每一条都环环相扣。如果你在面试中把这几条顺出来面试官基本不会再追问优化细节。4. 常见问题与避坑实录4.1 踩过的坑把 bitCount 当成了字符串长度我见过不少人在算完掩码后顺手用Integer.bitCount(mask)去代替长度理由是“掩码里每一位代表一个字母1 的个数不就是字母个数吗”。这句话听着挺有理其实是把“字母种类数”和“字符串长度”混为一谈。aaa的掩码只有最低一位是 1bitCount是 1但它的实际长度是 3。如果题目算的是“种类乘积”那倒无所谓可它要的是length(words[i]) * length(words[j])这是原始字符串的长度。掩码从来没有携带过重复计数信息它在构造时就被设计为“存在性”而非“计数性”。所以无论在哪一版实现里长度都必须单独存、单独取永远不要从掩码反推长度。4.2 踩过的坑排序剪枝时掩码和长度错位第二版和第三版都有排序操作这里是最容易出隐性 bug 的地方。比如有人先建了masks数组和lens数组然后只对lens做了降序排序masks还停留在原始顺序。此时内层循环看到的长度虽然是降序但掩码和长度根本对不上号判断条件里用到的mask是另一个单词的配对的正确性直接被破坏。更隐蔽的是如果lens和masks都各自排序但排序规则不一致比如一个降序一个升序那也会得到乱序配对。我给出的方案是从一开始就把(len, mask)打包成同一个数组元素或元组保证排序过程中它俩永远不分离。这个习惯可以避免一整类难以定位的问题。还有一点剪枝的break只适用于内层外两层都以长度降序为准的循环。如果你改用哈希表遍历或者外层固定的是最短单词千万不能照搬这个条件。4.3 踩过的坑空串、单元素数组与初始值题目允许words[i].length() 0吗在力扣这道题的约束里是允许的。空串的掩码是 0长度是 0。空串与其他任何单词做“无共同字母”的判断时都是合规的因为空集与任何集合的交集为空但它参与计算的乘积永远是 0所以不会对最大值产生影响。真正需要注意的反而是一开始初始化ans的方式。如果你把ans初始化为负数或者Integer.MIN_VALUE那么空串配对产生的 0 反而可能被当成一个“正确答案”返回题目实际期望在没有合规配对时返回 0这样就会出错。因此初始值请务必明确写为 0。同理words只有一个元素时双层循环压根进不去直接返回 0所有单词都共享同一个字母a时任意两个掩码按位与非零同样返回 0。这些都是合法结果不是异常。4.4 排查技巧对拍测试与问题速查表刷题时我最推荐的对拍式调试方法写一个简单的暴力解法作为基准再写一个优化解法然后用随机数据反复对比两个解法的输出是否一致。生成几个样例、几十组样例、上千组样例只要有一组不一致就立刻暴露优化代码里隐藏的错误。这个方法在验证排序剪枝、去重逻辑时特别好用因为手工构造的小数据往往晒不出问题随机数据反而容易撞见边界。下面是一张我总结的问题速查表现象可能原因解决办法返回乘积比预期小排序剪枝时掩码与长度错位将(len, mask)打包排序结果在某些用例下偏小去重后未按长度排序就用了break去重后再排序或在去重后用全量枚举空串输入时结果异常ans初始值不是 0初始化为 0超时没用掩码还在逐个字符扫描预处理掩码用按位与判断5. 一点延伸位掩码思想还能解决什么问题这道题的核心是把“有限集合的存在性判断”压缩成整数位运算这个套路在力扣上远不止出现在 318 题。最经典的相关应用是字母异位词分组如果把每个字符串都转成一个 26 位掩码再对相同掩码分组就能在近似线性时间内完成分组而不需要两两比较是否异位。另一个典型的场景是“判断子集关系”如果想知道一个单词是不是另一个单词的“字母子集”可以用(maskA maskB) maskA来判断这恰好与本题判断“是否完全不相交”互为镜像。此外状态压缩动态规划里到处都是位掩码的身影枚举子集、判断某个状态是否合法、合并状态转移本质上都是在用整数上的位运算来描述“哪些元素已经被选过”这件事。我经常跟同事开玩笑说位掩码是力扣给刷题人的一份礼物它把所有关于“集合边界”的思考都压缩成一个整数上的常数时间操作。以后再遇到“字母不超过 26 个”“元素不超过 32 个”这类题目第一反应就应该是——能不能用位做记号这类题目见得多了你自然会形成一种“看见有限集合就想按位编码”的条件反射。最后分享一个我在实际刷题中的体会与其死记这道题的代码不如把“为什么可以用位运算”这个问题彻底想透。一旦想透了你会发现它只是位掩码思想的一个小应用后面再碰到类似问题代码几乎可以顺手拈来。勤写对拍、勤分析复杂度比我当初一道题背十遍要高效得多。