Sunday, February 7, 2016

Leetcode 318: Maximum Product of Word Length

February 7, 2016

There are a several of stages to go through on Leetcode 318 problem solving today. 

10 minutes to read question and think about solution, confused about requirement(以为包括子字符串) ->
20 minutes to read blogs to understand solutions -> 
10 minutes to know the detail to implement (1) -> 
20 minutes to implement without bugs (2) -> 
10 minutes to implement with more clear code with bugs (3) -> 
10 minutes debug to read code again, debugging to pinpoint bug -> 
60 minutes to work on a better idea - optimal idea (5) -> 
work on exceeded time issues (20 minutes, instead of 60+ minutes) (6)

Action items:
1. Always work on coding, using Visual Studio. Try to improve coding. 

Leetcode 318: Maximum Product of Word Length 
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.
https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/ 

Solution 1:
直接看看每个字符串都包括了哪个字符,然后一一枚举是否有交集:
  • 有交集,则乘积为0
  • 无交集,乘积为 words[i].length() * words[j].length()
Julia's practice: 

Solution 2:
其实因为全部都是小写的字母,用int 就可以存储每一位的信息。这就是位运算
  • elements[i] |= 1 << (words[i][j] – ‘a’);   //把words[i][j] 在26字母中的出现的次序变为1
  •  elements[i] & elements[j]    // 判断是否有交集只需要两个数 按位 与 (AND)运算即可
read the blog to understand bit operation, take some time to refresh the memory:
http://www.cnblogs.com/onlyac/p/5155881.html


在一个字符串组成的数组words中,找出max{Length(words[i]) * Length(words[j]) },其中words[i]和words[j]中没有相同的字母,在这里字符串由小写字母a-z组成的。
对于这道题目我们统计下words[i]的小写字母a-z是否存在,然后枚举words[i]和words[j],找出max{Length(words[i]) * Length(words[j]) }。

小写字母a-z是26位,一般统计是否存在我们要申请一个bool flg[26]这样的数组,但是我们在这里用int代替,int是32位可以替代flg数组,用 与(&),或(1),以及向左移位(<<)就能完成。如“abcd” 的int值为 0000 0000 0000 0000 0000 0000 0000 1111,“wxyz” 的int值为 1111 0000 0000 0000 0000 0000 0000 0000,这样两个进行与(&)得到0, 如果有相同的字母则不是0。
Here is julia's practice:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_B.cs

Read the webpage about precedence and order of evaluation:
https://msdn.microsoft.com/en-us/library/2bxt6kc4.aspx

Solution 3:
Just for fun, write another version of bit manipulation implementation, but Julia created 3 bugs in the row before she writes a correct version.
Instead of using two words do not contain same char,
if ((s1 & s2) == 0) return true;

she tried to write a version to check any char from a to z, one by one check version:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_C.cs

Design takes practice. She thought about and then wrote, and then failed 3 times!


No comments:

Post a Comment