题目概述:给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母。如果不存在这样的两个单词,返回 0 。
解题思路1:暴力做法+小优化。直接两重循环枚举所有组合,再写一个函数判断两个字符串是否含有相同字符。
时间复杂度:\(O(n^3)\),加了个小优化居然就过了
代码:
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int res = 0;
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(i == j)continue;
else if(words[i].length() * words[j].length() <= res)continue;//小优化
else if(check(words[i],words[j])){
res = Math.max(res,words[i].length() * words[j].length());
}
}
}
return res;
}
public boolean check(String a,String b){
for(int i = 0; i < a.length(); i ++){
if(b.contains(a.charAt(i) + ""))return false;
}
return true;
}
}
正解:上述做法在判断两个字符串是否含有相同字符时,需要O(n)的时间复杂度。那么能不能对其进行优化呢?答案是肯定的,我们可以将每个单词都转化为一个二进制串,在判断两个字符串是否含有相同字符时,只需判断这两个字符串对应的二进制经过与(&)操作后是否为0,如果为0说明无重复字符,否则有重复字符。这样就可以使用O(1)的时间复杂度来判断两个字符串是否含有相同字符了。并且本题限制,只有小写字符,所以,int类型就能够存储。
时间复杂度:\(O(n^2)\)
代码:
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int res = 0;
int masks[] = new int[n];
for(int i = 0; i < n; i ++){
int len = words[i].length();
for(int j = 0; j < len; j ++){
//将单词转化为二进制,26个字母对应26位二进制,该位为1仅当该单词含有该位对应的单词
masks[i] |= 1 << (words[i].charAt(j) - 'a');
}
}
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(i == j)continue;
else if((masks[i] & masks[j]) == 0)res = Math.max(res,words[i].length() * words[j].length());
}
}
return res;
}
}
标签:字符,乘积,int,单词,length,words,字符串,长度
From: https://www.cnblogs.com/dengch/p/17815837.html