String Compression
Implement a method to perform string compression using the counts of repeated characters. If the “compressed” string would not become smaller than the original, return the original string.
Assume that the string has only upper and lower case letters (a-z)
Example
1
2
Input: aabcccccaaa
Output: a2b1c5a3
Solution
Complexity: (to store the output)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def compress(st):
result = bytearray() # Bytearray is mutable
if len(st) == 0:
return result
count = 1
current = st[0]
result.append(current)
for idx in xrange(1, len(st)):
if st[idx] == current:
count += 1
else:
result.append(str(count))
count = 1
current = st[idx]
result.append(current)
result.append(str(count))
if len(result) > len(st):
return st
return result
st = 'aabcccccaaa'
print 'Result:', compress(st)
Result: a2b1c5a3
