318. Maximum Product of Word Lengths

  • 42.8%

https://leetcode.com/problems/maximum-product-of-word-lengths/?tab=Description

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.

1
2
3
4
Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".
1
2
3
4
Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".
1
2
3
4
Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

cpp


https://discuss.leetcode.com/topic/31766/bit-shorter-c

Bit shorter C++

Same algorithm as most, just written a bit shorter.

1
2
3
4
5
6
7
8
9
10
11
12
int maxProduct(vector<string>& words) {
vector<int> mask(words.size());
int result = 0;
for (int i=0; i<words.size(); ++i) {
for (char c : words[i])
mask[i] |= 1 << (c - 'a');
for (int j=0; j<i; ++j)
if (!(mask[i] & mask[j]))
result = max(result, int(words[i].size() * words[j].size()));
}
return result;
}

Update: Here’s an O(n+N) variation, where n is the number of words and N is the total number of characters in all words. Thanks to junhuangli for the suggestion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProduct(vector<string>& words) {
unordered_map<int,int> maxlen;
for (string word : words) {
int mask = 0;
for (char c : word)
mask |= 1 << (c - 'a');
maxlen[mask] = max(maxlen[mask], (int) word.size());
}
int result = 0;
for (auto a : maxlen)
for (auto b : maxlen)
if (!(a.first & b.first))
result = max(result, a.second * b.second);
return result;
}

Or: (thanks to junhuangli’s further comment)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProduct(vector<string>& words) {
unordered_map<int,int> maxlen;
int result = 0;
for (string word : words) {
int mask = 0;
for (char c : word)
mask |= 1 << (c - 'a');
maxlen[mask] = max(maxlen[mask], (int) word.size());
for (auto maskAndLen : maxlen)
if (!(mask & maskAndLen.first))
result = max(result, (int) word.size() * maskAndLen.second);
}
return result;
}

https://discuss.leetcode.com/topic/31753/116ms-c-solution-use-early-pruning-faster-than-most-o-n-2

116ms c++ solution use early pruning (faster than most O(N^2))

Sort the vector first according to the length of string. Then use some early pruning to fasten the process.

The worst cases would still be O(N^2). It’s faster than most O(N^2) solutions. I don’t know whether we can do better. (Binary Search Seems Not work here) Any comments is welcomed.

Update: We can use counting sort to improve the time complexity of sorting to O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int maxProduct(vector<string>& words) {
int s=words.size();
if(s==0) return 0;
vector<int> bit(s,0);
sort(words.begin(), words.end(), compare); //sort the vector from longest to shortest
for(int i=0; i<s; i++){ //bit manipulation
for(int j=0; j<words[i].size(); j++) bit[i] |=(1<<(words[i][j]-'a'));
}
int maxlength=0;
for(int i=0; i<s-1; i++){
int si=words[i].size();
if(si*si<=maxlength) break; //early pruning
for(int j=i+1; j<s; j++){
int sj=words[j].size();
if(si*sj<=maxlength) break; //early pruning
if((bit[i]&bit[j])==0) maxlength=si*sj;
}
}
return maxlength;
}
static bool compare(string a, string b){
return a.size()>b.size();
}
};

https://discuss.leetcode.com/topic/40001/c-25-lines-96ms-straight-forward-solution

C++, 25 lines, 96ms, straight-forward solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int set_bit(string& str){
int mybits = 0;
for (char c : str){
mybits |= (1 << (c-'a'));
if ((mybits == 0x3FFFFFF)) break;
}
return mybits;
}

int maxProduct(vector<string>& words) {
int m_val = 0, w_size = words.size();
int m[w_size], m_w_size[w_size];

for(int i = 0; i < w_size; i++) {
m[i] = set_bit(words[i]);
m_w_size[i] = words[i].size();
}

for (int i = 0; i < w_size; i++)
for (int j = i+1; j < w_size; j++)
if ((m[i] & m[j])==0)
m_val = max((int)(m_w_size[i] * m_w_size[j]), m_val);

return m_val;
}
};

python


https://discuss.leetcode.com/topic/46685/python-solution-beats-99-67

Python solution, beats 99.67%

1
2
3
4
5
6
7
8
9
class Solution(object):
def maxProduct(self, words):
d = {}
for w in words:
mask = 0
for c in set(w):
mask |= (1 << (ord(c) - 97))
d[mask] = max(d.get(mask, 0), len(w))
return max([d[x] * d[y] for x in d for y in d if not x & y] or [0])

java


https://discuss.leetcode.com/topic/35539/java-easy-version-to-understand

JAVA———-Easy Version To Understand!!!!!!!!!!!!!!!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int maxProduct(String[] words) {
if (words == null || words.length == 0)
return 0;
int len = words.length;
int[] value = new int[len];
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 i = 0; i < len; i++)
for (int j = i + 1; j < len; j++) {
if ((value[i] & value[j]) == 0 && (words[i].length() * words[j].length() > maxProduct))
maxProduct = words[i].length() * words[j].length();
}
return maxProduct;
}

https://discuss.leetcode.com/topic/31769/32ms-java-ac-solution

32ms Java AC solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
public int maxProduct(String[] words) {
int max = 0;

Arrays.sort(words, new Comparator<String>(){
public int compare(String a, String b){
return b.length() - a.length();
}
});

int[] masks = new int[words.length]; // alphabet masks

for(int i = 0; i < masks.length; i++){
for(char c: words[i].toCharArray()){
masks[i] |= 1 << (c - 'a');
}
}

for(int i = 0; i < masks.length; i++){
if(words[i].length() * words[i].length() <= max) break; //prunning
for(int j = i + 1; j < masks.length; j++){
if((masks[i] & masks[j]) == 0){
max = Math.max(max, words[i].length() * words[j].length());
break; //prunning
}
}
}

return max;
}
}

https://discuss.leetcode.com/topic/31739/bit-manipulation-java-o-n-2

Bit manipulation Java O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public int maxProduct(String[] words) {
int max = 0;
int[] bytes = new int[words.length];
for(int i=0;i<words.length;i++){
int val = 0;
for(int j=0;j<words[i].length();j++){
val |= 1<<(words[i].charAt(j)-'a');
}
bytes[i] = val;
}
for(int i=0; i<bytes.length; i++){
for(int j=i+1; j<bytes.length; j++){
if((bytes[i] & bytes[j])==0)max = Math.max(max,words[i].length()*words[j].length());
}
}
return max;
}
}

Pre-process the word, use bit to represent the words. We can do this because we only need to compare if two words contains the same characters.

谢谢你,可爱的朋友。