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: 

https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength.cs

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!