Decode String Medium 0 attempts
LeetCode ↗

Decode String

Medium GraphBFSDFS LeetCode

You're given an encoded string such as "3[a2[c]]" and need to expand it back out. The rule k[encoded_string] means that encoded_string should appear repeated k times in a row, and these rules can be nested inside one another.

Input Format
Implement decodeString(s). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
s = "3[a]2[bc]"
Output
"aaabcbc"

Example 2

Input
s = "3[a2[c]]"
Output
"accaccacc"
Constraints
  • 1 <= s.length <= 30
  • Input encoding is valid; repeat counts lie in [1,300].
  • The decoded output has at most 10^5 characters.
Test Cases (2)
Case 1
Args: ["3[a]2[bc]"] Expected: "aaabcbc"
Case 2
Args: ["3[a2[c]]"] Expected: "accaccacc"
Topics
GraphBFSDFS

Stack-Based Parsing

Use stacks to track multiplier and current string at each nesting level.

javascript
function decodeString(s) {
  const numStack = [], strStack = [];
  let curr = '', num = 0;
  for (const c of s) {
    if (c >= '0' && c <= '9') num = num * 10 + (c - '0');
    else if (c === '[') { numStack.push(num); strStack.push(curr); num = 0; curr = ''; }
    else if (c === ']') { curr = strStack.pop() + curr.repeat(numStack.pop()); }
    else curr += c;
  }
  return curr;
}

Time: O(output length) | Space: O(output length)

Saved in this browser only. Private to you.

JavaScript