Decode a Bracketed Repetition String

medium string stack

Problem

Expand strings of the form k[chunk], where k is a positive integer count and chunk is itself an arbitrarily nested encoding. Use a stack of (count, partial string) frames; on '[' push, on ']' pop and repeat.

Inputs = "2[a3[b]]"

Output"abbbabbb"

Inner 3[b] expands to "bbb"; then 2[abbb] expands to "abbbabbb".

def decode(s):
    stack = []
    cur = ""
    num = 0
    for c in s:
        if c.isdigit(): num = num * 10 + int(c)
        elif c == '[': stack.append((num, cur)); num = 0; cur = ""
        elif c == ']': k, prev = stack.pop(); cur = prev + cur * k
        else: cur += c
    return cur

function decode(s) {
  const stack = []; let cur = "", num = 0;
  for (const c of s) {
    if (/\d/.test(c)) num = num * 10 + Number(c);
    else if (c === '[') { stack.push([num, cur]); num = 0; cur = ""; }
    else if (c === ']') { const [k, prev] = stack.pop(); cur = prev + cur.repeat(k); }
    else cur += c;
  }
  return cur;
}

class Solution {
    public String decode(String s) {
        Deque<Object[]> stack = new ArrayDeque<>();
        StringBuilder cur = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            else if (c == '[') { stack.push(new Object[]{ num, cur }); num = 0; cur = new StringBuilder(); }
            else if (c == ']') { Object[] f = stack.pop(); int k = (int) f[0]; StringBuilder prev = (StringBuilder) f[1]; StringBuilder rep = new StringBuilder(); for (int i = 0; i < k; i++) rep.append(cur); cur = prev.append(rep); }
            else cur.append(c);
        }
        return cur.toString();
    }
}

string decode(string s) {
    stack<pair<int, string>> st;
    string cur = "";
    int num = 0;
    for (char c : s) {
        if (isdigit(c)) num = num * 10 + (c - '0');
        else if (c == '[') { st.push({ num, cur }); num = 0; cur = ""; }
        else if (c == ']') { auto [k, prev] = st.top(); st.pop(); string rep; for (int i = 0; i < k; i++) rep += cur; cur = prev + rep; }
        else cur += c;
    }
    return cur;
}

Time: O(|output|) Space: O(depth · max chunk)