教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是 AlgoNote算法通关手册对 LeetCode 0318. 最大单词长度乘积 的完整题解。题目本质上是一道「字符串集合求交」问题核心技巧是利用 26 个小写字母与 32 位整数的天然对应关系用位掩码Bitmask压缩每个单词的字符集合再用一次按位与运算完成任意两个单词是否含相同字符的判断。读完本文你将掌握位掩码压缩字符集合的建模方法、1 k与运算的落地写法、两重循环求最大值的实现以及基于「掩码去重 长度取最大」的优化思路。题目背景与出处本题在仓库题解体系中的位置题解文档docs/solutions/0300-0399/maximum-product-of-word-lengths.md同章节题解索引docs/solutions/0300-0399/index.md全量题目列表题号 标签 难度docs/00_preface/00_05_solutions_list.md按算法分类的练习清单位运算题目一栏docs/00_preface/00_06_categories_list.md此外同一道题目还以「LCR 005」编号收录在剑指 Offer 专项突击版中题解见 docs/solutions/LCR/aseY1I.md两篇题解的思路与代码完全一致。也就是说掌握本篇解法可以同时解决两个平台的题目。题目标签位运算、数组、字符串难度中等。题目大意给定一个字符串数组words其中每个字符串只包含英语小写字母a~z。要求计算当两个字符串words[i]和words[j]不包含相同字符时它们长度乘积的最大值。如果不存在任何一对不含相同字符的字符串返回0。示例与边界情况若words [abcw, baz, foo, bar, xtfn, abcdef]则abcw与xtfn不含相同字符长度乘积为4 × 4 16是全局最大值应返回16。若所有字符串两两之间都含有相同字符例如words [aaa, aa, a]则返回0。单个字符串长度、字符串数量都可能很大题目数据规模由力扣给出因此算法复杂度需要认真设计。核心难点与朴素思路本题唯一的难点在于如何快速判断任意两个字符串之间是否包含相同字符。最直接的做法是遍历第一个字符串的每个字符再遍历第二个字符串逐个比对是否有相同字符。这一步单次判重的时间复杂度为 $O(L_1 \times L_2)$其中 $L_1$、$L_2$ 为两个字符串的长度再加上两层循环枚举所有字符串对 $O(n^2)$整体复杂度高达 $O(n^2 \times L^2)$在数据规模较大时必然超时。思考优化方向题目给出一个非常强的约束——字符串只包含 26 种小写字母。这意味着每个单词的「字符集合」本质上是一个最多 26 个元素的集合完全可以用一个 26 位的二进制数来表示。而一个32位的int整数恰好有 32 个二进制位每一个二进制位都可以表示一种字符的有无。于是单词abc的字符集合{a, b, c}→ 二进制第 0、1、2 位为1其余为0两个单词是否有相同字符 → 对两个整数做按位与结果非0即有相同字符结果为0即无相同字符。这样单次「判重」操作就从字符级的两层遍历压缩成一条机器指令级的整数运算时间复杂度从 $O(L_1 \times L_2)$ 降为 $O(1)$。这种「用整数二进制位表示集合、用位运算代替集合运算」的手法正是位运算在状态压缩领域的经典应用。仓库的 docs/07_algorithm/07_06_bit_operation.md 章节系统讲解了按位与、按位或、左移等六种基础位运算及其常用操作如1 k置位、x y掩码提取本题就是该理论章节的典型实战习题。位掩码建模详解由于只有 26 种小写字母我们为每个字母分配一个固定的二进制位a对应第 0 位掩码值为1 0 1b对应第 1 位掩码值为1 1 2c对应第 2 位掩码值为1 2 4……z对应第 25 位掩码值为1 25。通用的位编号计算公式为1 (ord(ch) - ord(a))。其中ord(ch)返回字符的 ASCII 码ord(ch) - ord(a)把字母映射到0 ~ 25的编号1 k则把第k位置为1。遍历单词中的每个字符不断用按位或把这些位累加进一个整数最终这个整数就是该单词字符集合的位掩码abc→1 | 2 | 4 7二进制000...00111def→8 | 16 | 32 56二进制000...0111000。两个掩码做按位与7 56 0说明abc与def没有相同字符若掩码同为7的两个单词例如abc与cab7 7 7 ! 0说明有相同字符。26 种字符只需 26 位天然落在32位int的容量之内因此每个掩码都能用一个普通整型变量安全存放不需要任何额外的大整数类型。参考实现位掩码 双重循环以下代码完整继承自原题解并补充了逐行注释class Solution: def maxProduct(self, words: List[str]) - int: size len(words) # arr[i] 存储 words[i] 的字符集合位掩码初始全 0 arr [0 for _ in range(size)] # 第一轮为每个单词构建 26 位掩码 for i in range(size): word words[i] len_word len(word) for j in range(len_word): # 把第 (ord(word[j]) - ord(a)) 位置为 1并通过按位或累加 arr[i] | 1 (ord(word[j]) - ord(a)) # 第二轮两两比较掩码求长度乘积最大值 ans 0 for i in range(size): for j in range(i 1, size): # 按位与结果为 0 说明两个字符集合无交集 if arr[i] arr[j] 0: k len(words[i]) * len(words[j]) ans k if ans k else ans return ans代码关键点逐条拆解掩码构建1 (ord(word[j]) - ord(a))一次生成单字符对应的位掩码arr[i] | ...是arr[i] arr[i] | ...的简写用按位或把新字符位并入已有集合。由于同一字符多次出现只会反复置同一个位aaa的掩码和a完全一样这正符合「字符集合」语义。判重语句if arr[i] arr[j] 0:。在 Python 中按位与的优先级高于比较运算符因此该表达式等价于(arr[i] arr[j]) 0即「两个掩码按位与的结果为零」→「两单词无共同字符」。为可读性考虑建议实际编码时显式写成if (arr[i] arr[j]) 0:效果相同。对称性剪枝内层循环从j i 1开始只枚举i j的字符串对避免(i, j)与(j, i)重复计算。最大值维护用三目表达式ans k if ans k else ans维护历史最大值ans初始为0保证「没有合法字符串对」时正确返回0。复杂度分析阶段时间复杂度空间复杂度掩码构建$O(n \times L)$$n$ 为字符串个数$L$ 为单词平均长度$O(n)$ 用于arr数组两两比较$O(n^2)$每次比较是 $O(1)$ 的整数按位与$O(n)$ 复用arr数组整体时间复杂度 $O(n^2 n \times L)$空间复杂度 $O(n)$。相比朴素的 $O(n^2 \times L^2)$省去了判重时的字符级遍历这是本题收益最大的优化点。进阶优化掩码去重保留每种掩码的最大长度位掩码还有一个可利用的性质字符集合相同的单词其掩码完全相同例如abc、abcc、cba的掩码都是7。在求「长度乘积最大值」时对同一种掩码只有长度最长的那个单词才可能产生更大的乘积其余单词可以忽略。因此可以用一个哈希表字典把「掩码 → 该掩码下的最大单词长度」做压缩把参与两两比较的单词数量从 $n$ 降到「不同掩码数 $m$」当单词数量大、字符集合高度重复时收益明显。实现如下class Solution: def maxProduct(self, words: List[str]) - int: # 掩码 - 该掩码下最长的单词长度 mask_to_max_len {} for word in words: mask 0 for ch in word: mask | 1 (ord(ch) - ord(a)) if mask not in mask_to_max_len or len(word) mask_to_max_len[mask]: mask_to_max_len[mask] len(word) ans 0 masks list(mask_to_max_len.keys()) for i in range(len(masks)): for j in range(i 1, len(masks)): if (masks[i] masks[j]) 0: product mask_to_max_len[masks[i]] * mask_to_max_len[masks[j]] ans max(ans, product) return ans该优化版本与原版的核心建模一致mask | 1 (ord(ch) - ord(a))、mask1 mask2 0判无交集只是额外用字典压缩了冗余单词两轮循环都在更少的对象上进行。举一反三仓库中同类的位运算题目本题归类于仓库的「位运算」算法主题。以下题目分布在 docs/00_preface/00_06_categories_list.md 的位运算题目列表中与该题共用「用位表示状态、用位运算代替集合运算」的思想适合配套练习0338. 比特位计数统计0 ~ n每个数字二进制中1的个数可配合x (x - 1)技巧。0136. 只出现一次的数字利用异或运算a ^ a 0的性质找唯一出现一次的数。0371. 两整数之和只用位运算实现整数加法体会进位与异或的分工。0089. 格雷编码相邻编码只有一位不同的序列构造与二进制位密切相关。0190. 颠倒二进制位 与 0191. 位 1 的个数位运算基础操作练习。底层理论可回顾 docs/07_algorithm/07_06_bit_operation.md 中的六种基础位运算规则以及「将指定位设置为 1」x | (1 k)、「按位与取交集」等常用操作总结表。小结LeetCode 0318及 LCR 005的关键收获有三点建模遇到「元素种类少、需要频繁比较集合」的问题优先考虑用整数位掩码压缩集合26 个小写字母恰好对应 26 个二进制位32位int完全够用。判重maskA maskB 0一次运算即可断定两集合无交集把判重从 $O(L^2)$ 降到 $O(1)$。剪枝同掩码只保留最长单词用字典进一步压缩参与比较的单词数量。掌握位掩码这一招不仅在本题得分更能迁移到「状态压缩动态规划」「子集枚举」「集合求交」等一大类高频面试问题中。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 454. 四数相加 II 精讲两两分组 哈希表把 O(N⁴) 降到 O(N²)LeetCode 454. 四数相加 II 精讲两两分组 哈希表把 O N⁴ 降到 O N² 导读 本文以本仓库 problems/454.4 sum i文档教程知识库除自身以外数组的乘积LeetCode 0238题解前缀乘积 × 后缀乘积两次遍历法O(n) 时间 O(1) 空间除自身以外数组的乘积LeetCode 0238题解前缀乘积 × 后缀乘积两次遍历法O n 时间 O 1 空间 本文是「算法通关手册AlgoNote」教程文档知识库本地视频播放怎么弄wiliwili 掌机影音指南本地视频播放怎么弄wiliwili 掌机影音指南 先说个反直觉的Switch 离线看片卡不卡瓶颈往往不在播放器而在你那张 SD 卡的等级——U1 的卡配音视频桌面应用上一篇gh_mirrors/v41/v4中的渐进式增强策略从基础到高级体验下一篇Uber Go 编码规范字符串与字节切片的高效转换创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考