Algorithm
Problem Name: 318. Maximum Product of Word Lengths
Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.
Example 1:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"] Output: 16 Explanation: The two words can be "abcw", "xtfn".
Example 2:
Input: words = ["a","ab","abc","d","cd","bcd","abcd"] Output: 4 Explanation: The two words can be "ab", "cd".
Example 3:
Input: words = ["a","aa","aaa","aaaa"] Output: 0 Explanation: No such pair of words.
Constraints:
2 <= words.length <= 10001 <= words[i].length <= 1000words[i]consists only of lowercase English letters.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int maxProduct(char** words, int wordsSize) {
char *s;
int *b, *l; // bits and length
int i, j;
int x, k = 0;
if (wordsSize < 2) return 0;
b = calloc(wordsSize * 2, sizeof(int));
//assert(b);
l = &b[wordsSize];
i = 0;
while (i < wordsSize) {
s = words[i];
while (s && *s) {
b[i] |= 1 << (*s - 'a');
l[i] ++;
s ++;
}
j = 0;
while (j < i) {
if ((b[j] & b[i]) == 0) {
x = l[j] * l[i];
if (k < x) k = x;
}
j ++;
}
i ++;
}
free(b);
return k;
}
Input
words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output
16
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int maxProduct(vector<string>& words) {
int maxlen = 0;
for(int i = 0; i < words.size(); i++)
for(int j = i + 1; j < words.size(); j++){
if(words[i].size() * words[j].size() <= maxlen) continue;
if(noCommon(words[i], words[j])) maxlen = max(maxlen, (int)(words[i].size() * words[j].size()));
}
return maxlen;
}
bool noCommon(string& a, string& b){
for(auto x: a)
for(auto y: b)
if(x == y> return false;
return true;
}
};
Input
words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output
16
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int maxProduct(String[] words) {
int maxProd = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if (noCommonLetters(words[i], words[j])) {
maxProd = Math.max(maxProd, words[i].length() * words[j].length());
}
}
}
return maxProd;
}
private boolean noCommonLetters(String s1, String s2) {
int bitMaskOne = 0;
int bitMaskTwo = 0;
for (char c : s1.toCharArray()) {
bitMaskOne |= 1 << ((int) c - (int) 'a');
}
for (char c : s2.toCharArray()) {
bitMaskTwo |= 1 << ((int) c - (int) 'a');
}
return (bitMaskOne & bitMaskTwo) == 0;
}
}
Input
words = ["a","ab","abc","d","cd","bcd","abcd"]
Output
4
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const maxProduct = function(words) {
if (words == null || words.length === 0) return 0;
let len = words.length;
let value = [];
for (let i = 0; i < len; i++) {
let tmp = words[i];
value[i] = 0;
for (let j = 0; j < tmp.length; j++) {
value[i] |= 1 << (tmp.charAt(j).charCodeAt(0) - "a".charCodeAt(0));
}
}
let maxProductNum = 0;
for (let i = 0; i < len; i++)
for (let j = i + 1; j < len; j++) {
if (
(value[i] & value[j]) === 0 &&
words[i].length * words[j].length > maxProductNum
)
maxProductNum = words[i].length * words[j].length;
}
return maxProductNum;
};
Input
words = ["a","ab","abc","d","cd","bcd","abcd"]
Output
4
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxProduct(self, words):
sets, mx = {w: set(w) for w in words}, 0
words.sort(key = len, reverse = True)
for i in range(len(words) - 1):
for j in range(i + 1, len(words)):
if len(words[i]) * len(words[j]) <= mx:
break
elif not sets[words[i]] & sets[words[j]]:
mx = len(words[i]) * len(words[j])
return mx
Input
words = ["a","aa","aaa","aaaa"]