Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a string s, consisting of digits and lowercase alphabet characters, that’s a run-length encoded string, return its decoded version. Note: The original string is guaranteed not to have numbers in it.
Constraints
0 ≤ n ≤ 100,000 where n is the length of s
Example 1
Input
s = “4a3b2c1d2a”
Output
“aaaabbbccdaa”Hint:Try to add x number of characters to a string where x is a number occurred before character
Run-Length Data Decompression Algorithm
The original data does not numbers, therefore we can just iteratre over the runlength encoded string, separate the count and data, push two to one array, and then finally reconstruct the original data.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def solve(self, s): c = 0 data = [] for i in s: if i.isdigit(): c = c * 10 + ord(i) - 48 else: data.append(c) data.append(i) c = 0 return "".join(data[i] * data[i + 1] for i in range(0, len(data), 2)) |
class Solution: def solve(self, s): c = 0 data = [] for i in s: if i.isdigit(): c = c * 10 + ord(i) - 48 else: data.append(c) data.append(i) c = 0 return "".join(data[i] * data[i + 1] for i in range(0, len(data), 2))
The time and space complexity is O(N) where N is the number of the characters in the encoded runlength string. We don’t consider the decoded original string obviously. The compressed string could be a few bytes but the decompressed string could be a lot more lengthy.
Run-length Encoding algorithm is simple: Teaching Kids Programming – Run-Length Encoding/Compression Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - The Fisher–Yates Random Shuffle Algorithm in Python
Next Post: Teaching Kids Programming - Run-Length Encoding/Compression Algorithm