Skip to content

Commit e9632aa

Browse files
fishercoder1534fishercoder1534
committed
refactor 318
1 parent 1cd67d2 commit e9632aa

File tree

1 file changed

+22
-94
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+22
-94
lines changed

‎src/main/java/com/fishercoder/solutions/_318.java

Lines changed: 22 additions & 94 deletions
Original file line numberDiff line numberDiff line change
@@ -23,113 +23,41 @@ Given a string array words, find the maximum value of length(word[i]) * length(w
2323
Return 0
2424
No such pair of words.*/
2525
public class _318 {
26-
//Inspired by this awesome post: https://discuss.leetcode.com/topic/35539/java-easy-version-to-understand
27-
//Idea: this question states that all words consisted of lower case (total only 26 unique chars),
28-
//this is a big hint that we could use integer (total 32 bits) to represent each char
29-
//values[i] means how many unique characters this string words[i] has
30-
public int maxProduct(String[] words) {
31-
if (words == null || words.length == 0) {
32-
return 0;
33-
}
34-
int len = words.length;
35-
int[] values = new int[len];
36-
for (int i = 0; i < words.length; i++) {
37-
String word = words[i];
38-
for (int j = 0; j < words[i].length(); j++) {
39-
values[i] |= 1 << (word.charAt(j) - 'a');//the reason for left shift by this number "word.charAt(j) -'a'" is for 'a', otherwise 'a' - 'a' will be zero and 'a' will be missed out.
40-
}
41-
}
42-
int maxProduct = 0;
43-
for (int i = 0; i < words.length; i++) {
44-
for (int j = 0; j < words.length; j++) {
45-
//check if values[i] AND values[j] equals to zero, this means they share NO common chars
46-
if ((values[i] & values[j]) == 0 && words[i].length() * words[j].length() > maxProduct) {
47-
maxProduct = words[i].length() * words[j].length();
48-
}
49-
}
50-
}
51-
return maxProduct;
52-
}
53-
54-
//This is still failed due to TLE, O(n^3) algorithm is the core defect, you'll have to come up with a faster one!
55-
public int maxProduct_with_pruning(String[] words) {
56-
int maxProduct = 0;
57-
//use a customized comparator to make the words list sorted in descending order, brilliant!
58-
Arrays.sort(words, (o1, o2) -> {
59-
if (o1.length() > o2.length()) {
60-
return -1;
61-
} else if (o1.length() < o2.length()) {
62-
return 1;
63-
} else {
26+
public static class Solution1 {
27+
//Inspired by this awesome post: https://discuss.leetcode.com/topic/35539/java-easy-version-to-understand
28+
//Idea: this question states that all words consisted of lower case (total only 26 unique chars),
29+
//this is a big hint that we could use integer (total 32 bits) to represent each char
30+
//values[i] means how many unique characters this string words[i] has
31+
public int maxProduct(String[] words) {
32+
if (words == null || words.length == 0) {
6433
return 0;
6534
}
66-
});
67-
for (int i = 0; i < words.length - 1; i++) {
68-
String currWord = words[i];
69-
int currWordLen = currWord.length();
70-
if (maxProduct > currWordLen * words[i + 1].length()) {
71-
break;//pruning
72-
}
73-
char[] chars = currWord.toCharArray();
74-
Set<Character> set = new HashSet();
75-
for (char c : chars) {
76-
set.add(c);
77-
}
78-
for (int j = i + 1; j < words.length; j++) {
79-
char[] chars2 = words[j].toCharArray();
80-
boolean valid = true;
81-
for (char c : chars2) {
82-
if (set.contains(c)) {
83-
valid = false;
84-
break;
85-
}
35+
int len = words.length;
36+
int[] values = new int[len];
37+
for (int i = 0; i < words.length; i++) {
38+
String word = words[i];
39+
for (int j = 0; j < words[i].length(); j++) {
40+
values[i] |= 1 << (word.charAt(j)
41+
- 'a');//the reason for left shift by this number "word.charAt(j) -'a'" is for 'a', otherwise 'a' - 'a' will be zero and 'a' will be missed out.
8642
}
87-
if (valid) {
88-
int thisWordLen = words[j].length();
89-
maxProduct = Math.max(maxProduct, thisWordLen * currWordLen);
90-
}
91-
}
92-
}
93-
return maxProduct;
94-
}
95-
96-
/**
97-
* My natural idea is an O(n^3) algorithm, I thought of Trie, but I don't think it applies well to this question.
98-
* This following algorithm made it pass 173/174 test cases, as expected, failed by the last extreme test cases due to TLE.
99-
*/
100-
public int maxProduct_most_brute_force(String[] words) {
101-
int maxProduct = 0;
102-
for (int i = 0; i < words.length - 1; i++) {
103-
String currWord = words[i];
104-
int currWordLen = currWord.length();
105-
char[] chars = currWord.toCharArray();
106-
Set<Character> set = new HashSet();
107-
for (char c : chars) {
108-
set.add(c);
10943
}
110-
for (int j = i + 1; j < words.length; j++) {
111-
char[] chars2 = words[j].toCharArray();
112-
boolean valid = true;
113-
for (char c : chars2) {
114-
if (set.contains(c)) {
115-
valid = false;
116-
break;
44+
int maxProduct = 0;
45+
for (int i = 0; i < words.length; i++) {
46+
for (int j = 0; j < words.length; j++) {
47+
//check if values[i] AND values[j] equals to zero, this means they share NO common chars
48+
if ((values[i] & values[j]) == 0
49+
&& words[i].length() * words[j].length() > maxProduct) {
50+
maxProduct = words[i].length() * words[j].length();
11751
}
11852
}
119-
if (valid) {
120-
int thisWordLen = words[j].length();
121-
maxProduct = Math.max(maxProduct, thisWordLen * currWordLen);
122-
}
12353
}
54+
return maxProduct;
12455
}
125-
return maxProduct;
12656
}
12757

12858
public static void main(String... strings) {
12959
_318 test = new _318();
13060
String[] words = new String[]{"abcw", "baz", "foo", "bar", "xtfn", "abcdef"};
131-
// System.out.println(test.maxProduct_with_pruning(words));
132-
// System.out.println(test.maxProduct(words));
13361

13462
//The following is to understand what does left shift by 1 mean:
13563
//the tricky part is to understand how it's written for me:

0 commit comments

Comments
 (0)