318. 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"]
Return0
No such pair of words.

[leetcode 318] Maximum Product of Word Lengths

这道题要求找出两个没有重复字符的单词,且这两个单词长度的乘积最大,如果找不到,返回0。
一见到这道题,想到的就是如何去重,比如先将第一个单词和其它单词比较,如果有相同的,就将短的单词去除,但是这样就出现一个问题,比如有三个单词abcd,dfghjklmn,fqzp,显然如果按上面的方法,会剩下一个,返回0,但是1和3明显是满足条件的。于是不能删除,只能用一个唯一标示符来表示单词,而且如果两个单词之间没有相同的单词可以通过运算该标示符来知道,那么怎么做呢,就是位运算。
具体的,每一个字符减去a后的结果都在0-26之间,那么用一个整形表示一个单词,其每一位表示对应字符是否出现,这样如果两个单词没有出现相同的字符,其对应的整形相与的结果就是0,这样问题就解决了,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxProduct(String[] words) {
if(words==null||words.length==0)return 0;
int[]values=new int[words.length];
for(int i=0;i<words.length;i++){
for(int j=0;j<words[i].length();j++)values[i]|=1<<(words[i].charAt(j)-'a');
}
int maxLength=0;
for(int i=0;i<values.length;i++){
for (int j=i+1;j<values.length;j++){
if((values[i]&values[j])==0){
int temp=words[i].length()*words[j].length();
if(temp>maxLength)maxLength=temp;
}
}
}
return maxLength;
}

如果觉得有帮助,给我打赏吧!