Decode String
Medium · Stack & Strings · String · Stack · Recursion
Problem
A string is encoded with the rule k[text]: the part inside the brackets is written out k times in a row. Rules can nest, so 3[a2[c]] means acc three times, accaccacc. Given an encoded string s, return it decoded.
s is always well formed: the brackets match, every [ comes straight after a whole number k ≥ 1, and digits appear only in those counts, never in the text itself. A count can have more than one digit, as in 12[ab], and letters can sit before, between and after groups at any level.
Examples
Input: s = "3[a]2[bc]" Output: "aaabcbc"
a three times, then bc twice.
Input: s = "3[a2[c]]" Output: "accaccacc"
Inside out: 2[c] is cc, so a2[c] is acc, and three of those make accaccacc.
Constraints
- 1 <= len(s) <= 30
- s consists of lowercase English letters, digits and square brackets
- s is a valid encoding; every count k is a whole number with 1 <= k <= 300
- the decoded string is at most 10^5 characters long
Approaches
- Expand the innermost group, again and again — time O(g · (n + L)), space O(n + L)
Related problems
Start free on Cariara · Coding problems · System design studio
