LeetCode 318 - Maximum Product of Word Lengths

作者 QIFAN 日期 2016-12-24
LeetCode 318 - Maximum Product of Word Lengths

原题链接:318. Maximum Product of Word Lengths


题目

给一组字符串数组,求不含相同字母的字符串的最大乘积。

思路

大致思路是这样:对数组降序排序,逐个判断是否包含,再找最大乘积。这样最差时间复杂度是 $O(n^2)$ (当所有字符串都包含相同字母)。

试了一圈后发现,提高速度的关键就在于判断两个字符串是否有相同字母。

有一个位运算的方法就是将一个字符串以一个 26 位的二进制表示,’a’ 是第一位,’b’ 第二位,1 代表有,0 代表无。所以在比较时只需相互进行和(“&”),若结果为 0 则互不包含。

代码:

public class Solution {
public int maxProduct(String[] words) {
if (words == null || words.length <= 1) {
return 0;
}
Arrays.sort(words, new Comparator<String>() {
public int compare(String s1, String s2) {
return s2.length() - s1.length();
}
});
int[] value = new int[words.length]
for (int i = 0; i < len; i++) {
String tmp = words[i];
value[i] = 0;
for (int j = 0; j < tmp.length(); j++) {
value[i] |= 1 << (tmp.charAt(j) - 'a');
}
}
int maxProduct = 0;
for (int out = 0; out < words.length - 1; out++) {
for (int in = out + 1; in < words.length; in++) {
// if (hasSameChar(words[in], words[out])) {
if (value[in] & value[count] != 0)
continue;
}
int product = words[out].length() * words[in].length();
if (product > maxProduct) {
maxProduct = product;
}
break;
}
}
return maxProduct;
}
// 非位运算比较
public boolean hasSameChar(String str1, String str2){
for(char c : str1.toCharArray()){
if(str2.indexOf(c) >= 0 ) return true;
}
for(char c : str2.toCharArray()){
if(str1.indexOf(c) >= 0 ) return true;
}
return false;
}
}