教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇指南基于 LogicStack-LeetCode 仓库中「剑指 Offer II」系列的题解文档完整讲解「单词长度的最大乘积」这道位运算经典题如何用 26 位掩码把一个单词的字符集压缩进一个 int用一次运算判定两个单词是否共字母并进一步用哈希表对相同掩码去重优化。读完后你能独立掌握「位掩码表示集合」这一通用技巧并能对同类集合交集判定问题给出 $O(n^2)$ 内可接受的高效实现。一、题目描述与数据范围这是 LeetCode 上的一道中等难度题题目 Tag 为「模拟」「位运算」给定一个字符串数组words请计算当两个字符串words[i]和words[j]不包含相同字符时它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串返回 $0$。示例 1:输入: words [abcw,baz,foo,bar,fxyz,abcdef] 输出: 16 解释: 这两个单词为 abcw, fxyz。它们不包含相同字符且长度的乘积最大。示例 2:输入: words [a,ab,abc,d,cd,bcd,abcd] 输出: 4 解释: 这两个单词为 ab, cd。示例 3:输入: words [a,aa,aaa,aaaa] 输出: 0 解释: 不存在这样的两个单词。数据范围决定了解法选型后面会用到$2 words.length 1000$$1 words[i].length 1000$words[i]仅包含小写字母从数据规模看$n \le 1000$ 意味着 $O(n^2)$ 级别的枚举是可以接受的而仅含小写字母这个约束正是把字符集塞进一个整数的关键前提。二、模拟解法把每个单词压成一个 26 位掩码根据题意进行模拟即可。核心观察是每个words[i]只包含小写字母而判定两个单词是否包含相同字符本质上只需要知道每个字母是否出现过与出现次数无关。于是可以用一个int来代表某个words[i]低 26 位分别代指字母a-z是否出现过。对于单词中的每个字符w.charAt(i)计算它相对a的偏移u w.charAt(i) - a再执行t | (1 u)把对应位置 1。这样单词abcw→ 位 0、1、2、22 置 1单词fxyz→ 位 5、23、24、25 置 1两者按位与为 $0$说明没有公共字母可以参与乘积计算。反过来任意两个掩码a b ! 0就意味着两个单词至少共享一个字母这一对直接跳过。这样公共字母判定从逐字符比较退化成了一次整数按位与开销是常数。完整 Java 代码如下与仓库题解一致class Solution { public int maxProduct(String[] words) { int n words.length, idx 0; int[] masks new int[n]; for (String w : words) { int t 0; for (int i 0; i w.length(); i) { int u w.charAt(i) - a; t | (1 u); } masks[idx] t; } int ans 0; for (int i 0; i n; i) { for (int j 0; j i; j) { if ((masks[i] masks[j]) 0) ans Math.max(ans, words[i].length() * words[j].length()); } } return ans; } }代码分两个阶段预处理阶段逐单词扫描、置位得到masks数组每个masks[i]是对应单词的字符集掩码枚举阶段双层循环枚举所有下标对(i, j)j i避免重复配对与自配对掩码按位与为 $0$ 时更新答案words[i].length() * words[j].length()。ans初始为 $0$天然覆盖了不存在合法单词对时直接返回 $0$ 的分支对应示例 3。复杂度分析时间复杂度令 $n$ 为words数组的长度转换出masks的复杂度为 $O(\sum_{i 0}^{i n - 1}words[i].length)$得到答案的复杂度为 $O(n^2)$。整体复杂度为 $O(\max(\sum_{i 0}^{i n - 1}words[i].length, n^2))$。空间复杂度$O(n)$masks数组。在本题 $n \le 1000$ 的约束下$O(n^2)$ 约为 $10^6$ 量级的配对检查每对只做一次运行毫无压力。三、优化解法用哈希表对相同掩码去重模拟解法有一个可压缩的冗余如果两个单词的字符集完全相同即mask值相等比如abc和bca那么在与其它单词配对时只有长度更长的单词才有价值——短的那个无论和谁配对乘积都不可能超过长的它。因此可以用哈希表MapInteger, Integer掩码 → 该掩码对应单词的最大长度代替masks数组枚举阶段只在去重后的掩码集合内进行双重循环class Solution { public int maxProduct(String[] words) { MapInteger, Integer map new HashMap(); for (String w : words) { int t 0, m w.length(); for (int i 0; i m; i) { int u w.charAt(i) - a; t | (1 u); } if (!map.containsKey(t) || map.get(t) m) map.put(t, m); } int ans 0; for (int a : map.keySet()) { for (int b : map.keySet()) { if ((a b) 0) ans Math.max(ans, map.get(a) * map.get(b)); } } return ans; } }与模拟解法逐行对比变化集中在两处建表逻辑if (!map.containsKey(t) || map.get(t) m) map.put(t, m);同一掩码只保留最大单词长度实现等掩码去重枚举对象从n个下标变为map.keySet()中的掩码值乘积改用map.get(a) * map.get(b)。复杂度方面建表仍为 $O(\sum_{i 0}^{i n - 1}words[i].length)$枚举阶段最坏仍是 $O(n^2)$当所有掩码互不相同时退化为原始规模整体复杂度为 $O(\max(\sum_{i 0}^{i n - 1}words[i].length, n^2))$空间复杂度 $O(n)$。在存在大量字符集相同、仅长度不同的单词时例如示例 3 的[a,aa,aaa,aaaa]全部坍缩成同一个掩码去重后枚举对数会显著减少常数上更优而最坏情况两者同阶所以两种写法在本题数据范围内都是可靠的。顺带一提优化解法中枚举(a, b)时a与b允许相同同一掩码自配对时a b a ! 0除非掩码为 $0$不会出现非法自配对不会引入错误答案。四、技巧提炼与相关题解本题是「用位掩码表示集合 位与判定交集」这一模式的教科书式应用掌握后可以迁移到一大类问题集合编码字母表规模 $\le 26$ 时任何某字母是否出现的信息都可以压进一个 32 位int的低 26 位交集/子集判定a b 0判不相交a b a判a的字符集是b的子集puzzle类题目常用去重压缩相同掩码只保留最优最长值把 $n$ 个候选压成至多 $2^{26}$ 个不同掩码实践中远小于此。在 LogicStack-LeetCode 仓库中这道题的完整题解位于 剑指 Offer II 005. 单词长度的最大乘积中等。由于它与 LeetCode 318「最大单词长度乘积」本质上是同一道题题面与约束完全一致仅个别示例单词不同仓库中同样收录了对应题解318. 最大单词长度乘积中等两篇采用同一套模拟 哈希去重解法可对照阅读。此外本仓库按 Tag 维度维护了索引本题同时收录在位运算 Tag 索引可顺带复习1 u置位、交集判定等同类题如 137 只出现一次的数字 II、1178 猜字谜等均是掩码技巧的变体模拟 Tag 索引以按题意枚举 状态压缩视角归类同类题。若继续深入位运算技巧同目录下的 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数简单 展示了 i 1逐位扫描与动态规划计数两种风格与本篇的掩码构建方式互为补充。五、小结解法核心数据结构枚举规模时间复杂度空间复杂度模拟位掩码数组int[] masks$n^2$ 对下标$O(\max(\sum words[i].length, n^2))$$O(n)$哈希去重MapInteger, Integer去重后掩码对$O(\max(\sum words[i].length, n^2))$$O(n)$本题的价值在于把两个字符串是否共字母这一 $O(\min(len_i, len_j))$ 的字符级比较通过位掩码预处理摊薄成一次整数按位与再叠加相同掩码只留最长单词的哈希去重使枚举空间进一步收缩。这套字符集 → 掩码 → 位与判定的思路是处理小字母表集合类问题的标准武器建议在掌握本篇后沿仓库的位运算索引继续练习同类题。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐Dexter面向深度金融研究的自主 Agent —— 安装、运行、评估与调试全指南Dexter面向深度金融研究的自主 Agent —— 安装、运行、评估与调试全指南 Dexter 是一个专注于金融研究的自主智能体autonomous ag教程文档AlgoNote 题解LeetCode 0318 最大单词长度乘积 —— 用位掩码把「两两判重」从 O(L²) 降到 O(1)AlgoNote 题解LeetCode 0318 最大单词长度乘积 —— 用位掩码把「两两判重」从 O L² 降到 O 1 本文是 AlgoNote算法通关教程文档知识库LeetCode-Book 剑指 Offer 48 详解最长不含重复字符的子字符串的三种解法动态规划、哈希表与双指针LeetCode Book 剑指 Offer 48 详解最长不含重复字符的子字符串的三种解法动态规划、哈希表与双指针 本文基于 LeetCode Book示例工程上一篇30分钟搞定NativeScript开发环境与项目创建从入门到实战下一篇30分钟搞懂线性回归从数学公式到西瓜书实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
 项目介绍,路由配置,vant组件库的下载和使用)
` 的声明式请求校验：express-validator 模式化验证完全指南)
