|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.Arrays; |
| 4 | +importjava.util.Comparator; |
| 5 | +importjava.util.HashSet; |
| 6 | +importjava.util.Set; |
| 7 | + |
| 8 | +importutils.CommonUtils; |
| 9 | + |
| 10 | +/**318. Maximum Product of Word Lengths QuestionEditorial Solution My Submissions |
| 11 | +Total Accepted: 29054 |
| 12 | +Total Submissions: 71485 |
| 13 | +Difficulty: Medium |
| 14 | +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. |
| 15 | +
|
| 16 | +Example 1: |
| 17 | +Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] |
| 18 | +Return 16 |
| 19 | +The two words can be "abcw", "xtfn". |
| 20 | +
|
| 21 | +Example 2: |
| 22 | +Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"] |
| 23 | +Return 4 |
| 24 | +The two words can be "ab", "cd". |
| 25 | +
|
| 26 | +Example 3: |
| 27 | +Given ["a", "aa", "aaa", "aaaa"] |
| 28 | +Return 0 |
| 29 | +No such pair of words.*/ |
| 30 | +publicclassMaximumProductOfWordLengths { |
| 31 | +//Inspired by this awesome post: https://discuss.leetcode.com/topic/35539/java-easy-version-to-understand |
| 32 | +//Idea: this question states that all words consisted of lower case (total only 26 unique chars), |
| 33 | +//this is a big hint that we could use integer (total 32 bits) to represent each char |
| 34 | +//values[i] means how many unique characters this string words[i] has |
| 35 | +publicintmaxProduct(String[]words){ |
| 36 | +if(words ==null ||words.length ==0)return0; |
| 37 | +intlen =words.length; |
| 38 | +int[]values =newint[len]; |
| 39 | +for(inti =0;i <words.length;i++){ |
| 40 | +Stringword =words[i]; |
| 41 | +for(intj =0;j <words[i].length();j++){ |
| 42 | +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. |
| 43 | + } |
| 44 | + } |
| 45 | +intmaxProduct =0; |
| 46 | +for(inti =0;i <words.length;i++){ |
| 47 | +for(intj =0;j <words.length;j++){ |
| 48 | +//check if values[i] AND values[j] equals to zero, this means they share NO common chars |
| 49 | +if((values[i] &values[j]) ==0 &&words[i].length() *words[j].length() >maxProduct)maxProduct =words[i].length()*words[j].length(); |
| 50 | + } |
| 51 | + } |
| 52 | +returnmaxProduct; |
| 53 | + } |
| 54 | + |
| 55 | +//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! |
| 56 | +publicintmaxProduct_with_pruning(String[]words) { |
| 57 | +intmaxProduct =0; |
| 58 | +//use a customized comparator to make the words list sorted in descending order, brilliant! |
| 59 | +Arrays.sort(words,newComparator<String>(){ |
| 60 | +@Override |
| 61 | +publicintcompare(Stringo1,Stringo2) { |
| 62 | +if(o1.length() >o2.length())return -1; |
| 63 | +elseif(o1.length() <o2.length())return1; |
| 64 | +elsereturn0; |
| 65 | + } |
| 66 | + }); |
| 67 | +for(inti =0;i <words.length-1;i++){ |
| 68 | +StringcurrWord =words[i]; |
| 69 | +intcurrWordLen =currWord.length(); |
| 70 | +if(maxProduct >currWordLen *words[i+1].length())break;//pruning |
| 71 | +char[]chars =currWord.toCharArray(); |
| 72 | +Set<Character>set =newHashSet(); |
| 73 | +for(charc :chars)set.add(c); |
| 74 | +for(intj =i+1;j <words.length;j++){ |
| 75 | +char[]chars2 =words[j].toCharArray(); |
| 76 | +booleanvalid =true; |
| 77 | +for(charc :chars2){ |
| 78 | +if(set.contains(c)) { |
| 79 | +valid =false; |
| 80 | +break; |
| 81 | + } |
| 82 | + } |
| 83 | +if(valid){ |
| 84 | +intthisWordLen =words[j].length(); |
| 85 | +maxProduct =Math.max(maxProduct,thisWordLen*currWordLen); |
| 86 | + } |
| 87 | + } |
| 88 | + } |
| 89 | +returnmaxProduct; |
| 90 | + } |
| 91 | + |
| 92 | +/**My natural idea is an O(n^3) algorithm, I thought of Trie, but I don't think it applies well to this question. |
| 93 | + * This following algorithm made it pass 173/174 test cases, as expected, failed by the last extreme test cases due to TLE.*/ |
| 94 | +publicintmaxProduct_most_brute_force(String[]words) { |
| 95 | +intmaxProduct =0; |
| 96 | +for(inti =0;i <words.length-1;i++){ |
| 97 | +StringcurrWord =words[i]; |
| 98 | +intcurrWordLen =currWord.length(); |
| 99 | +char[]chars =currWord.toCharArray(); |
| 100 | +Set<Character>set =newHashSet(); |
| 101 | +for(charc :chars)set.add(c); |
| 102 | +for(intj =i+1;j <words.length;j++){ |
| 103 | +char[]chars2 =words[j].toCharArray(); |
| 104 | +booleanvalid =true; |
| 105 | +for(charc :chars2){ |
| 106 | +if(set.contains(c)) { |
| 107 | +valid =false; |
| 108 | +break; |
| 109 | + } |
| 110 | + } |
| 111 | +if(valid){ |
| 112 | +intthisWordLen =words[j].length(); |
| 113 | +maxProduct =Math.max(maxProduct,thisWordLen*currWordLen); |
| 114 | + } |
| 115 | + } |
| 116 | + } |
| 117 | +returnmaxProduct; |
| 118 | + } |
| 119 | + |
| 120 | +publicstaticvoidmain(String...strings){ |
| 121 | +MaximumProductOfWordLengthstest =newMaximumProductOfWordLengths(); |
| 122 | +String[]words =newString[]{"abcw","baz","foo","bar","xtfn","abcdef"}; |
| 123 | +// System.out.println(test.maxProduct_with_pruning(words)); |
| 124 | +// System.out.println(test.maxProduct(words)); |
| 125 | + |
| 126 | +//The following is to understand what does left shift by 1 mean: |
| 127 | +//the tricky part is to understand how it's written for me: |
| 128 | +// "x << y" means left shift x by y bits |
| 129 | +//left shift is equivalent to multiplication of powers of 2, so "4 << 1" equals to " 4 * 2^1" |
| 130 | +//similarly, "4 << 3" equals to "4 * 2^3" which equals "4 * 8" |
| 131 | +Stringsample ="f"; |
| 132 | +intbits =0,shiftLeftByHowMany =0,shiftLeftResult =0; |
| 133 | +for(intj =0;j <sample.length();j++){ |
| 134 | +shiftLeftByHowMany =sample.charAt(j) -'a'; |
| 135 | +shiftLeftResult =1 <<shiftLeftByHowMany; |
| 136 | +bits |=1 << (sample.charAt(j) -'a');//this means shift left 1 by "sample.charAt(j) -'a'" bits |
| 137 | +System.out.println("nonShiftLeft = " +shiftLeftByHowMany +"\tnonShiftLeft binary form is: " +Integer.toBinaryString(shiftLeftByHowMany) |
| 138 | + +"\nshiftLeft = " +shiftLeftResult +"\tshiftLeft binary form is: " +Integer.toBinaryString(shiftLeftResult) |
| 139 | + +"\nbits = " +bits +"\tbits binary form is: " +Integer.toBinaryString(bits)); |
| 140 | +System.out.println(shiftLeftResult == (1 *Math.pow(2,shiftLeftByHowMany))); |
| 141 | + } |
| 142 | + |
| 143 | +//similarly, right shift is written like this: "x >> y", means shift x by y bits |
| 144 | +//4 >> 3 equals 4 * 2^3, see below: |
| 145 | +System.out.println(4*8 == (4 *Math.pow(2,3))); |
| 146 | + } |
| 147 | +} |