Decode String Medium 0 attempts
LeetCode ↗

Decode String

Medium GraphBFSDFS LeetCode

Given an encoded string like "3[a2[c]]", decode it. The encoding rule is: k[encoded_string] means the encoded_string is repeated k times.

Example: s = "3[a2[c]]" → Output: "accaccacc"

Sample Input
—
Sample Output
—
Constraints
  • 1 <= s.length <= 30
  • s consists of lowercase letters, digits, [ and ]
  • All integers in s are in range [1, 300]
Test Cases
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.

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