【第三轮】6.16-6.22 CareerCup 1.5

1.5 Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.


回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

小柯西 发表于 2014-6-19 01:44
- -我的回复也不光是针对你23楼的讨论的。。
那既然是取平均复杂度。。再回到你这道题的算法，我也不觉 ...

这道题空间复杂度确实不是O(1)，这个没错。。。

【解题思路】: 写了两种实现方式：纯 C-string 的操作，也支持"aaaaaaaaaaaab"和普通"aaaabbccd"的 test case
                                               利用C++ string object, 主要是 concatenate 直接用 ‘+’ 就行了，比较简洁和大家用java写的思路是一样的
                    之前一直对c-string 和 c++ string object不熟悉，导致这一章的一些题老是去用char array 操作，容易出错，代码也不简洁。 做到第五题才开窍。
【时间复杂度】
                     O(n)
【空间复杂度】
                     O(n)
【gist link】    看str_compress2(), 比较简洁！
                     https://gist.github.com/xun-gong/295dbd999829a0fc7aba

solution 1
Traverse each character in the string, compare the current char with the previous one, if equals, count++, otherwise, appends the previous char and count into the StringBuilder
[count: the occurrence of the same consecutive characters]
Time Complexity: O(n)
Space Complexity: O(n)
Tip: Here, we must use StringBuilder or StringBuffer rather than String. Because the String is immutable, every time we add a character into the string, it will create a new String and eventually the Time Complexity will be O(n^2)

solution 2
The same idea with the first solution
Improve: Instead check the length at the end, in this method, Scan first to count the length of the Compress String, if the length is large than the original, return original. In this way, do not need extra O(n) space to build the Compress String. Otherwise, more O(n) time needed to build Compress String, and the time Complexity will be O(2n)
Instead of using the StringBuilder, we use char[] to implements this method.
Time Complexity: O(n)
Space Complexity: O(1) or O(n)

The Code Link: http://www.jyuan92.com/post-316

【解题思路】
先检查是不是长度变短 变短就compress
＊＊没有解决出现超过10的问题呢 回头再看吧= =
【时间复杂度】
N
【空间复杂度】
N
【gist link】
https://gist.github.com/atlas1017/d53c4f08b2a7a942df4e
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
since we may need to return the original string, we cannot destroy it. So, create a new string to store the compression result, and compare their length to decide which string to return.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/qianhuang/77db3602a516a6a1da68

【解题思路】use int array of length 256 as a counter for each character and create a stringbuffer to build compressed string, length check is done before the final output
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/16b8e16d190c16ceb149
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】user-interaction is included in the code

【解题思路】
  Save the first character. Iterate and compare next character, increment count
  Concatenate character and count to a new string, return it if the length is shorter
【时间复杂度】
  O(N)
【空间复杂度】
  O(N)
【gist link】
  https://gist.github.com/habina/d3eabcba9c86e7855052
【test case】
  "aabcccccaaa "

【解题思路】
  Save the first character. Iterate and compare next character, increment count
  Concatenate character and count to a new string, return it if the length is shorter
【时间复杂度】
  O(N)
【空间复杂度】
  O(N)
【gist link】
https://gist.github.com/gaoyike/188d4e09eb110097b964
【test case】
  "aabcccccaaa "

jing0328 发表于 2014-6-16 13:49
【解题思路】use int array of length 256 as a counter for each character and create a stringbuffer to ...

aaaaaaaabbbbbbbbaa

your code : a10b8

should be : a8b8a2

jing0328 发表于 2014-6-16 13:49
【解题思路】use int array of length 256 as a counter for each character and create a stringbuffer to ...

aaaaaaaabbbbbbbbaa

your code : a10b8

should be : a8b8a2

jing0328 发表于 2014-6-16 13:49
【解题思路】use int array of length 256 as a counter for each character and create a stringbuffer to ...

aaaaaaaabbbbbbbbaa

your code : a10b8

should be : a8b8a2

readman 发表于 2014-6-16 14:38
aaaaaaaabbbbbbbbaa

your code : a10b8

哦哦哦 没仔细看题 谢谢指出来啊 我等会改改