[第二轮] 2/18-2/24 CareerCup 1.5

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

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

Build the new compressed string while traversing the string. Time complexity O(N).
https://gist.github.com/Zuohr/4972261

check all elements in leaner time. time O(n)

https://gist.github.com/njcongtou/4972684

zuohr 发表于 2013-2-18 01:02
Build the new compressed string while traversing the string. Time complexity O(N).
https://gist.git ...

1. I notice that you did not handle null check. e.g. input string is null.
2. try to use stringbuilder to concantenate string instead of using "+" two strings. just better performance in Java.
  

time complex O(n)

https://gist.github.com/mazl123321/4973668

scan string linearly, compare each character to its next, find continuous repeated characters and compress them in new string
return compressed string if it smaller than original one

https://gist.github.com/chrislukkk/4973683

https://gist.github.com/cqx83/4974004

traverse the whole string once. O(n)

jimwallet 发表于 2013-2-18 02:42
1. I notice that you did not handle null check. e.g. input string is null.
2. try to use stringbu ...

Thank you for your comment, I have updated my code in gist.

https://gist.github.com/Zuohr/4972261

zuohr 发表于 2013-2-18 01:02
Build the new compressed string while traversing the string. Time complexity O(N).
https://gist.git ...

Hi, I have a question. What's the result if the test case is "aaab"? I think that it is still "aaab" because the "compressed" string, "a3b1", is not smaller than the original string.

Transform origin string into new string by counting the number of different successive characteristics when the new string is smaller than origin one.
https://github.com/Tedatworking/ ... ster/20130217_5.cpp