Maximum Product of Word Lengths
Description
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".
Hint
Train of Thought
对每个单词,都用一个int来存它出现过的字母, 重复的算一个, 把这个二进制转成int存起来 再比较这些单词与的结果, 为0说明没有相同字母
optimize: 按长度从大到小排序, 这样最后求结果的时候当前找到的就一定是最大的
Code
public class Solution {
public int maxProduct(String[] words) {
int max = 0;
Arrays.sort(words, new Comparator<String>(){
public int compare(String a, String b){
return b.length() - a.length();
}
});
int[] masks = new int[words.length]; // alphabet masks
for(int i = 0; i < masks.length; i++){
for(char c: words[i].toCharArray()){
masks[i] |= 1 << (c - 'a');
}
}
for(int i = 0; i < masks.length; i++){
if(words[i].length() * words[i].length() <= max) break; //prunning, because it is sorted
for(int j = i + 1; j < masks.length; j++){
if((masks[i] & masks[j]) == 0){
max = Math.max(max, words[i].length() * words[j].length());
break; //prunning
}
}
}
return max;
}
}