A string is compressed as repeated <count><char> groups, e.g. 2c3a1t. The count
is a positive integer (possibly multiple digits) and is followed by a single
character to repeat. Return the uncompressed string.
uncompress(s)
Input format: the compressed string.
"2c3a1t" // → "ccaaat"
"1a1b1c" // → "abc"
"10e" // → "eeeeeeeeee"
The input is <count><char> groups glued together; expand each into count copies of char. The real difficulty is figuring out where one group ends and the next begins, especially since the count can be multiple digits (like 10 in 10e).
A single pointer stepping by a fixed amount has no way to know how far to jump, since groups aren't fixed width — 2c is two characters, 10e is three. You need to read the digits to know how long the numeric part is.
Use a group-start pointer marking the beginning of the current group, and a second pointer scanning forward through consecutive digits. The moment it lands on a non-digit, everything between the two pointers is the count, and that non-digit is the character to repeat.
Convert the digits to a number, append the character that many times, jump the group-start pointer past the character just consumed, and repeat until it reaches the end.
The digit-scanning pointer visits each character once searching for the end of a digit run, and the group-start pointer only moves forward. Parsing the whole input takes time proportional to its length — no re-scanning. The only extra work is proportional to the output size, since writing count copies necessarily takes count steps.
Regex or other pattern-matching shortcuts are doing the same two-pointer scan under the hood. Thinking of it explicitly as "a start marker and a scanning marker" makes the multi-digit-count edge case (like 10e) obvious to handle correctly.
def uncompress(s):
out = ""
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] >= "0" and s[j] <= "9":
j += 1
count = int(s[i:j])
ch = s[j]
out += ch * count
i = j + 1
return out
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.