Created
February 8, 2016 20:26
-
-
Save jianminchen/92430047f7fb89b81b5d to your computer and use it in GitHub Desktop.
Leetcode 318
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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! | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment