友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-03-24 20:39:51
*/
public int maxProduct(String[] words) {
Arrays.sort(words, Comparator.comparingInt(String::length));
Map<String, boolean[]> wordToChars = new HashMap<>(words.length);
int result = 0;
for (int i = words.length - 1; i > 0; i--) {
for (int j = i - 1; j >= 0; j--) {
int multi = words[i].length() * words[j].length();
// 优化
if (multi < result) {
continue;
}
boolean[] aChars = wordToChars.get(words[i]);
if (aChars == null) {
aChars = tagChars(words[i]);
wordToChars.put(words[i], aChars);
}
boolean[] bChars = wordToChars.get(words[j]);
if (bChars == null) {
bChars = tagChars(words[j]);
wordToChars.put(words[j], bChars);
}
boolean same = false;
for (int k = 0; k < 26; k++) {
if (aChars[k] && bChars[k]) {
same = true;
break;
}
}
if (!same) {
result = Math.max(result, multi);
}
}
}
return result;
}
private boolean[] tagChars(String words) {
boolean[] aChars = new boolean[26];
for (char c : words.toCharArray()) {
aChars[c - 'a'] = true;
}
return aChars;
}