Bit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int maxProduct(String[] words) {
int maxProduct = 0;
int[] masks = new int[words.length];
for (int i = 0; i < words.length; i++) {
String word = words[i];
for (int j = 0; j < word.length(); j++) {
masks[i] |= (1 << (word.charAt(j) - 'a'));
}
}
for (int i = 0; i < masks.length; i++) {
for (int j = i + 1; j < masks.length; j++) {
if ((masks[i] & masks[j]) == 0) {
maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
}
}
}
return maxProduct;
}
}
|
Bit
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
| class Solution {
public int maxProduct(String[] words) {
int maxProduct = 0;
Map<Integer, Integer> maskToMaxLengthMap = new HashMap<>();
for (String word : words) {
int mask = 0;
for (int j = 0; j < word.length(); j++) {
mask |= (1 << (word.charAt(j) - 'a'));
}
Integer prevLength = maskToMaxLengthMap.get(mask);
if (prevLength == null || word.length() > prevLength) {
maskToMaxLengthMap.put(mask, word.length());
}
}
Integer[] masks = maskToMaxLengthMap.keySet().toArray(new Integer[0]);
for (int i = 0; i < masks.length; i++) {
for (int j = i + 1; j < masks.length; j++) {
if ((masks[i] & masks[j]) == 0) {
maxProduct = Math.max(maxProduct, maskToMaxLengthMap.get(masks[i]) * maskToMaxLengthMap.get(masks[j]));
}
}
}
return maxProduct;
}
}
|
References
318. Maximum Product of Word Lengths
剑指 Offer II 005. 单词长度的最大乘积