forked from KnowledgeCenterYoutube/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
318_Maximum_Product_of_Word_Lengths
89 lines (76 loc) · 2.33 KB
/
318_Maximum_Product_of_Word_Lengths
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
Leetcode 318 : Maximum Product of Word Lengths
Detailed video explanation : https://youtu.be/E8Ctj36CzuY
================================================
C++:
----
class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
vector<int> word_int(n, 0);
vector<int> word_len(n, 0);
for(int i = 0; i < n; ++i){
string w = words[i];
int _len = w.length();
int w_int = 0;
for(int j = 0; j < _len; ++j)
w_int |= 1 << (w[j] - 'a');
word_int[i] = w_int;
word_len[i] = _len;
}
int max_product = 0;
for(int i = 0; i < n-1; ++i){
for(int j = i+1; j < n; ++j){
if((word_int[i] & word_int[j]) == 0)
max_product = max(max_product, word_len[i]*word_len[j]);
}
}
return max_product;
}
};
Java:
-----
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] word_int = new int[n];
int[] word_len = new int[n];
for(int i = 0; i < n; ++i){
String w = words[i];
int _len = w.length();
int w_int = 0;
for(int j = 0; j < _len; ++j)
w_int |= 1 << (w.charAt(j) - 'a');
word_int[i] = w_int;
word_len[i] = _len;
}
int max_product = 0;
for(int i = 0; i < n-1; ++i){
for(int j = i+1; j < n; ++j){
if((word_int[i] & word_int[j]) == 0)
max_product = Math.max(max_product, word_len[i]*word_len[j]);
}
}
return max_product;
}
}
Python3:
-------
class Solution:
def maxProduct(self, words: List[str]) -> int:
n = len(words)
word_int, word_len = [0]*n, [0]*n
for i in range(n):
w = words[i]
_len = len(w)
w_int = 0
for j in range(_len):
w_int |= 1 << (ord(w[j]) - ord('a'))
word_int[i] = w_int
word_len[i] = _len
max_product = 0
for i in range(n-1):
for j in range(i+1, n):
if((word_int[i] & word_int[j]) == 0):
max_product = max(max_product, word_len[i]*word_len[j])
return max_product