Medium

Decode String

LAB

Decode a string where k[encoded] repeats the bracketed section k times, including nested sections.

EXAMPLES

Example 1

Input
{
  "s": "3[a]2[bc]"
}

Output
"aaabcbc"

FUNCTION SHAPE

s: string→string

SOLUTION NOTE

Precompute bracket matching, then recursively parse. Similar pattern to calculator problems.

Reveal reference solution +

pythonREFERENCE

def decodeString(self, s: str) -> str:
    # Precompute matching brackets
    closing = {}
    stack = []
    for i, c in enumerate(s):
        if c == '[':
            stack.append(i)
        elif c == ']':
            closing[stack.pop()] = i

    def parse(left, right):
        res = []
        i = left
        while i <= right:
            if s[i].isalpha():
                res.append(s[i])
                i += 1
            elif s[i].isdigit():
                j = i
                while s[j].isdigit():
                    j += 1
                k = int(s[i:j])
                inner = parse(j + 1, closing[j] - 1)
                res.append(inner * k)
                i = closing[j] + 1
        return ''.join(res)

    return parse(0, len(s) - 1)

TimeO(n × max_k)

SpaceO(n)

Open on LeetCode ↗