Algorithm to Decode Run-Length Compression String

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:
s = “3[a]2[bc]”, return “aaabcbc”.
s = “3[a2[c]]”, return “accaccacc”.
s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.

This is to decompress using run-length algorithm. The square brackets can have nested square brackets inside each other, and we assume the input string is well-formed.

Decompress Run-length String using C++

We can use the result string as a stack. Push every thing that is not “]” to the string. And if it is “]” we need to rewind to find the corresponding (closest) numbers and “[“. The substrings are expanded in place in the following C++ run-length decompression implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    string decodeString(string s) {
        string res = "";
        for (const auto &c: s) {
            if (c != ']') {
                res.push_back(c);
                continue;
            }
            int idx = res.find_last_of('[');
            string sub = res.substr(idx + 1);
            int i = idx - 1;
            while ((i >= 0) && (isdigit(res[i]))) {
                -- i;
            }
            // get the numbers before []
            int count = std::stoi(res.substr(i + 1, idx - i));
            res = res.substr(0, i + 1);
            while (count -- > 0) {
                res += sub;
            }
        }
        return res;        
    }
};

class Solution {
public:
    string decodeString(string s) {
        string res = "";
        for (const auto &c: s) {
            if (c != ']') {
                res.push_back(c);
                continue;
            }
            int idx = res.find_last_of('[');
            string sub = res.substr(idx + 1);
            int i = idx - 1;
            while ((i >= 0) && (isdigit(res[i]))) {
                -- i;
            }
            // get the numbers before []
            int count = std::stoi(res.substr(i + 1, idx - i));
            res = res.substr(0, i + 1);
            while (count -- > 0) {
                res += sub;
            }
        }
        return res;        
    }
};

We use substr and std::stoi to convert the digit string to integer while you can also multiply and add the digits manually. The string.find_last_of tracks the last index of the character, which takes O(N) complexity. The overall complexity is O(KN) where K is the maximum number/integer that comes before the [] string.

–EOF (The Ultimate Computing & Technology Blog) —