原題網址:https://leetcode.com/problems/maximum-product-of-word-lengths/
Given a string array
words
, find the maximum value of
length(word[i]) * length(word[j])
where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:
Given
["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return
16
The two words can be
"abcw", "xtfn"
.
Example 2:
Given
["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return
4
The two words can be
"ab", "cd"
.
Example 3:
Given
["a", "aa", "aaa", "aaaa"]
Return
No such pair of words.
方法:可以通過直方圖統計來比較兩個單詞是否有共同的字母,但有個更快捷的方法就是使用26個比特來比較。
public class Solution {
private int hash(char[] wa) {
int hash = 0;
for(int i=0; i<wa.length; i++) {
hash |= (1<<(wa[i]-'a'));
}
return hash;
}
public int maxProduct(String[] words) {
char[][] was = new char[words.length][];
int[] hashes = new int[words.length];
for(int i=0; i<words.length; i++) {
was[i] = words[i].toCharArray();
hashes[i] = hash(was[i]);
}
int max = 0;
for(int i=0; i<words.length-1; i++) {
for(int j=i+1; j<words.length; j++) {
if ((hashes[i] & hashes[j]) == 0) {
int m = was[i].length * was[j].length;
if (m > max) max = m;
}
}
}
return max;
}
}
方法二:使用比特進行哈希。
public class Solution {
public int maxProduct(String[] words) {
int[] f = new int[words.length];
for(int i=0; i<words.length; i++) {
char[] wa = words[i].toCharArray();
for(int j=0; j<wa.length; j++) {
f[i] |= 1 << (wa[j]-'a');
}
}
int max = 0;
for(int i=0; i<words.length-1; i++) {
for(int j=i+1; j<words.length; j++) {
if ((f[i] & f[j]) == 0) max = Math.max(max, words[i].length() * words[j].length());
}
}
return max;
}
}