Julia's coding blog - Practice makes perfect: Leetcode 318: Maximum Product of Word Length

Julia's coding blog - Practice makes perfect: Leetcode 318: Maximum Product of Word Length

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。

Read full article from Julia's coding blog - Practice makes perfect: Leetcode 318: Maximum Product of Word Length