最大单词长度乘积( LeetCode 318 )
一、题目描述
给你一个字符串数组 words
,找出并返回 length(words[i]) * length(words[j])
的最大值,并且这两个单词不含有公共字母。如果不存在这样的两个单词,返回 0
。
示例 1:
输入:words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出:16
解释:这两个单词为 "abcw", "xtfn"。
示例 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]
仅包含小写字母
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最大单词长度乘积( LeetCode 318 ):https://leetcode-cn.com/problems/maximum-product-of-word-lengths/
class Solution {
public int maxProduct(String[] words) {
// 获取字符串数组的长度
int n = words.length;
// 创建一个与 words 同等长度的 masks
int[] masks = new int[n];
// 每一个字母是否出现在某个单词的状态用一个 int 表示, int 的每一位代表 a - z 中的每个字母是否出现过
// 比如 a 对应的是 000001
// 比如 b 对应的是 000010
// 比如 c 对应的是 000100
// 这样的话,ab 对应的是 000011
for (int i = 0 ; i < n ; i++) {
String word = words[i];
int bit = 0;
// 对于 word 中的每个字母来说,都拿出来查看
// 假设字符串为 "abc"
// 令字符串中的每一个字符命名为 c
// 则 (c - 'a') 为 0 1 2
// bit |= 1 << (c - 'a') 则是将 1 左移 0 位、1位、2位
// bit 开始位为 0
// 0 | 1 = 1
// 1 | 10 = 11
// 11 | 100 = 111
// 因此,字符串为 "abc" 对应的就是 111
for (int j = 0; j < word.length(); j++) {
int c = word.charAt(j) - 'a';
// bit |= 1 << (c - 'a') 则是将 1 左移 (c - 'a')位
bit |= (1 << c);
}
// 因此,字符串为 word 对应的就是 bit
masks[i] = bit;
}
// 开始计算最大值
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, words[i].length() * words[j].length());
}
}
}
// 返回结果
return ans;
}
}
2、C++ 代码
3、Python 代码