Decode a String

See all coding puzzles and patterns here.

Difficulty: Medium
Patterns:
- Stack

Problem Definition

You are given a string that is encoded to indicate the number of times a character or sequence repeats.

For example, 3[a] is the encoding for aaa, 3[a]2[b] is the encoding for aaabb, and 2[a2[b]] is the encoding for abbabb.

Write a function that will return the decoded string for such an encoding. For now, assume the encoding is properly formatted.

Examples

Some test cases to verify our solution.

assert decode("3[a]") == "aaa")
assert decode("3[a]2[b]") == "aaabb")
assert decode("3[a2[b]4[c]]") == "abbccccabbccccabbcccc")
assert decode("2[2[2[a]]]") == "aaaaaaaa")
assert decode("2[2[2[a]]]b") == "aaaaaaaab"
assert decode("2[2[2[a]]c]b") == "aaaacaaaacb"
assert decode("2[2[2[da]x]c]b") == "dadaxdadaxcdadaxdadaxcb"
assert decode("10[1[ab]]") == "abababababababababab"

Recursive Solution

Whenever we encounter a nested []>, we can do a recursive call to decode the contents of the nested [] and then recombine them in the calling stack frame.

def decode(s):
    if not s:
        return ""
    c = s[0]
    i = 1
    if c.isalpha():
        while i < len(s) and s[i].isalpha():
            c += s[i]
            i += 1
        return c + decode(s[i:])
    while s[i].isnumeric():
        c += s[i]
        i += 1
    times = int(c)
    buf = ""
    i += 1 # the first [
    brack_count = 1 # the first [
    while brack_count:
        if s[i] == "[":
            brack_count += 1
        elif s[i] == "]":
            brack_count -= 1
        buf += s[i]
        i += 1
    return times * decode(buf[:-1]) + decode(s[i:])

Recursive Solution Complexity

Let $n = $ len(s).

In the worst case, we are traversing the string $n$ times, so our runtime complexity should be $O(n^2)$.

In the worst case, we might create $\approx \frac{n}{2}$ stacks, and each stack creates a copy of length $\frac{n}{2}$, resulting in a space complexity of $O(n^2)$.

Stack-Based Solution

As the structure implies, we can use a stack to store prior sequences of characters and their multipliers as we jump into a [].

Once we're done with the processing the nested [], we can pop the previously stored element at the top of the stack and append the nested [] sequences as a character in the prior sequence of characters.

def decode(s):
    stack = []
    num, ans = 0, []
    for c in s:
        if c.isnumeric():
            num = 10 * num + int(c)
        elif c == "[":
            stack.append((num, ans))
            num, ans = 0, []
        elif c == "]":
            nested_chars = "".join(ans)
            num, ans = stack.pop()
            ans.append(num * nested_chars if num > 0 else nested_chars)
            num = 0
        else:
            ans.append(num * c if num > 0 else c)
            num = 0
    return "".join(ans)

Stack-Based Solution Complexity

Let $n =$ len(s).

Since we are traversing through the string once, runtime complexity should be $\Theta(n)$.