Teaching Kids Programming – Run-Length Decoding/Decompression Algorithm


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) —

GD Star Rating
loading...
366 words
Last Post: Teaching Kids Programming - The Fisher–Yates Random Shuffle Algorithm in Python
Next Post: Teaching Kids Programming - Run-Length Encoding/Compression Algorithm

The Permanent URL is: Teaching Kids Programming – Run-Length Decoding/Decompression Algorithm

Leave a Reply