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.
public static int maxProduct(String[] words){
int[] arri = new int[words.length];
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words[i].length(); j++) {
arri[i] |= 1<<(words[i].charAt(j)-'a');
}
}
int ans = 0;
for (int i = 0; i < words.length-1; i++) {
for (int j = i+1; j < words.length; j++) {
if ((arri[i] & arri[j]) == 0) {// 没有重复的字母
ans = Math.max(ans, words[i].length()*words[j].length());
}
}
}
return ans;
}
移位运算符：
1 << 0 => 1
1 << 1 => 2
1 << 2 => 4
1 << 3 => 8
1 << 4 => 16
1 << 5 => 32
1 << 6 => 64
1 << 7 => 128
1 << 8 => 256
1 << 9 => 512
1 << 10 => 1024
1 << 11 => 2048
1 << 12 => 4096
1 << 13 => 8192
1 << 14 => 16384
1 << 15 => 32768
1 << 16 => 65536
1 << 17 => 131072
1 << 18 => 262144
1 << 19 => 524288
1 << 20 => 1048576
1 << 21 => 2097152
1 << 22 => 4194304
1 << 23 => 8388608
1 << 24 => 16777216
1 << 25 => 33554432
words[i] 对应着arri[i]:words[i]中的每个单词编码后得到arri[i]
注释处相交等于0说明有重复字母。