原文链接: https://leetcode-cn.com/problems/maximum-product-of-word-lengths
英文原文
Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.
Example 1:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"] Output: 16 Explanation: The two words can be "abcw", "xtfn".
Example 2:
Input: words = ["a","ab","abc","d","cd","bcd","abcd"] Output: 4 Explanation: The two words can be "ab", "cd".
Example 3:
Input: words = ["a","aa","aaa","aaaa"] Output: 0 Explanation: No such pair of words.
Constraints:
2 <= words.length <= 10001 <= words[i].length <= 1000words[i]consists only of lowercase English letters.
中文题目
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
示例 1:
输入:["abcw","baz","foo","bar","xtfn","abcdef"]输出:16 解释: 这两个单词为"abcw", "xtfn"。
示例 2:
输入:["a","ab","abc","d","cd","bcd","abcd"]输出:4 解释:这两个单词为"ab", "cd"。
示例 3:
输入:["a","aa","aaa","aaaa"]输出:0 解释: 不存在这样的两个单词。
提示：
2 <= words.length <= 10001 <= words[i].length <= 1000words[i]仅包含小写字母
通过代码
高赞题解
模拟
根据题意进行模拟即可，利用每个 $words[i]$ 只有小写字母，且只需要区分两字符是否有字母重复。
我们可以使用一个 int 来代指某个 $word[i]$：低 $26$ 来代指字母 a-z 是否出现过。
然后对每个「字符对」所对应的两个 int 值执行 & 操作（若两字符无重复字符，则结果为 $0$），并得出最终答案。
代码：
[]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; } }
- 时间复杂度：令 $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)$
优化
不难发现，对于词频相同（$mask$ 值相等）的两字符，只需要保留字符长度大的即可，因此我们可以使用「哈希表」代替 $masks$ 数组。
代码：
[]class Solution { public int maxProduct(String[] words) { Map<Integer, 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; } }
- 时间复杂度：令 $n$ 为 $words$ 数组的长度，得到 $map$ 的复杂度为 $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)$
其他相关内容
1. 模拟
考虑加练如下「模拟」题目 🍭🍭
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
2. 位运算
考虑加练如下「位运算」题目 🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 137. 只出现一次的数字 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 190. 颠倒二进制位 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 191. 位1的个数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 231. 2 的幂 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 260. 只出现一次的数字 III | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 268. 丢失的数字 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 318. 最大单词长度乘积 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 338. 比特位计数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 342. 4的幂 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 371. 两整数之和 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 405. 数字转换为十六进制数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 461. 汉明距离 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 476. 数字的补数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 477. 汉明距离总和 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 526. 优美的排列 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 1178. 猜字谜 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
| 1711. 大餐计数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 剑指 Offer 15. 二进制中1的个数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 49802 | 67580 | 73.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
