【第三轮】6.16-6.22 CareerCup 1.5

【解题思路】
遍历原 string 建立新 string，比较二者长度选择返回值
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/fcbfaf6b4100d99918ea

【解题思路】
就是直接做，从前向后遍历。在循环的中间检查一下compressed之后的string是不是比原来的sting长，如果是的话就直接返回原来的string即可。
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_5-cc
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
None

【解题思路】Compare current character and its next character, if they are different or encounter the boundary, append it and its count to result. Otherwise increase the count by 1 and move to the next character.
【时间复杂度】O(n) for going through all the characters.
【空间复杂度】O(n) for storing the result string.
【gist link】https://gist.github.com/30d8ea8624913bf7c18f.git
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
input : " ". expect : " ". input : "". expect : "".
input : Null. expect : Null.
input : "a". expect : "a"

【解题思路】就是用计数器来计数，最后来比较大小
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/qiangusc/2769ad688dd4ffe386c9

【解题思路】遍历一遍字符串，用一个boolean标记是否第一次遇到该字符，第一次遇到append进StringBuilder里，然后计数，直到遇到不同的字符，将统计的次数append进StringBuilder里，重置boolean标记。
【时间复杂度】O(n)
【空间复杂度】StringBuilder可以自动扩容，average O(n)
【gist link】https://gist.github.com/chouclee/b57b6915366b87cdff44
【test case】"aaaaaaaaaaaaaaaaaaaaaaaa" ,"aaaaabbbbb      ","","abc","aaaabbbbc","呵呵呵呵呵呵","呵呵"

小柯西 发表于 2014-6-17 09:54
【解题思路】Compare current character and its next character, if they are different or encounter the ...

谢点评~
我的代码如果是处理全部相同字符的字符串，时间其实还是O(n)。可能我代码比较乱，不好意思~
fill the count那段确实写错了，已经修改。

小柯西 发表于 2014-6-17 09:54
【解题思路】Compare current character and its next character, if they are different or encounter the ...

还有，应该怎么写“点评”啊？点“回复“好像不对的样子。。

【解题思路】遍历一遍字符串，用两个char存放当前读取的字符和上一个字符。如果两者相等，计数加1。如果两者不等，写入当前计数到result中，然后将count设为0。然后更新两个char。 最后比较result和原字符串的长度。
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/asdw3276/8da1d8560fe3897442d8
【test case】""    " "   "a" "aa" "ab" "aaa"   "aaaaaabbbaaa" "aaaaaabbba"
感谢所有给我code review的小伙伴

【解题思路】
compare the current character with the previous one, if equals, cnt++, otherwise, appends the previous char and cnt to the stringbuffer and updates the previous char and cnt. cnt is the occurrence of the same consecutive characters. Once done, compare the length with the original one, if not less than the original one, return the original one.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/7fd763f020e29d9c482d

====================================
【Follow up Question】
Can you decompress the compressed string generated from your code? (In my case: NO), If not, how would you do that? (Thinking......)

【解题思路】
traverse the string directly and count #characters. Then check whether the result is smaller than input string.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/monkerek/b2051b2d48ccbcfe1db2