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 0
No such pair of words.
Analysis
Masks example:
- abcdef: 111111
- abcw: 10000000000000000000111
- xtfn: 100010000010000000100000
- a: 1
- aa: 1
- aaa: 1
- aaaa: 1
Code
public class Solution {
public int maxProduct(String[] words) {
int max = 0;
if (words==null || words.length==0) return 0;
//sort words to have the longest words in the front
Arrays.sort(words, new Comparator<String>(){
public int compare(String a, String b){
return b.length() - a.length();
}
});
//words with same chars will have same masks
//masks[] 代表，有某一个字母（不管出现多少次），相对应的位置上就是1，总用有26位
int[] masks = new int[words.length];
for (int i=0; i<words.length; i++){
for (char c:words[i].toCharArray()){
masks[i] |= 1 << (c-'a');
}
}
for (int i=0; i<words.length; i++){
if (words[i].length() * words[i].length() <= max) break; //prunning, impossible to find larger result
for (int j=i+1; j<words.length; j++){
//==0代表没有相同字母
if ((masks[i] & masks[j])==0){
max = Math.max(max, words[i].length() * words[j].length());
break; //no need to find other words for word[i], but cannot return!! Still need to go over i loop
}
}
}
return max;
}
}
Note:
- char c:words[i].toCharArray()
- if ((masks[i] & masks[j])==0): 注意 & 左右要加()
- The method for bit masks is really good!