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:
Input:["abcw","baz","foo","bar","xtfn","abcdef"]
Output:16The two words can be
Explanation:"abcw", "xtfn".
Example 2:
Input:["a","ab","abc","d","cd","bcd","abcd"]
Output:4The two words can be
Explanation:"ab", "cd".
Example 3:
Input:["a","aa","aaa","aaaa"]
Output:0No such pair of words.
Explanation:
class Solution {
public int maxProduct(String[] words) {
int[] checker = new int[words.length];
if (words == null || words.length == 0) {
return 0;
}
int res = 0;
for (int i = 0; i < words.length; i++) {
String word = words[i];
for (int j = 0; j < word.length(); j++) {
char curChar = word.charAt(j);
checker[i] |= 1 << curChar - 'a';
}
}
for (int i = 0; i < words.length - 1; i++) {
for (int j = i + 1; j < words.length; j++) {
if ((checker[i] & checker[j]) == 0) {
res = Math.max(res, words[i].length() * words[j].length());
}
}
}
return res;
}
}public class Solution {
public int largestProduct(String[] dict) {
// Write your solution here
Arrays.sort(dict, new Comparator<String>(){
@Override
public int compare(String a, String b) {
return b.length() - a.length();
}
});
int[] arr = new int[dict.length];
for (int i = 0; i < dict.length; i++) {
for (int j = 0; j < dict[i].length(); j++) {
arr[i] |= 1 << dict[i].charAt(j) - 'a';
}
}
int res = 0;
for (int i = 1; i < dict.length; i++) {
for (int j = 0; j < i; j++) {
if (dict[i].length() * dict[j].length() <= res) {
break;
}
if ((arr[i] & arr[j]) == 0) {
res = dict[i].length() * dict[j].length();
}
}
}
return res;
}
}