126. Decode String

Medium · String

You need to decode a string with nested repetition patterns. The input is an encoded string containing numbers followed by square brackets, where a number before brackets means repeat the contents that many times. For example, 3[a] means repeat 'a' three times to get 'aaa', and patterns can be nested like 3[a2[c]] which means repeat 'a' followed by 'c' repeated twice, three times total, giving 'accaccacc'. Parse the input string and return the fully decoded result.

Examples

Example 1
Input: "3[a]2[bc]"
Output: "aaabcbc"
Explanation: "aaa" + "bcbc"
Example 2
Input: "3[a2[c]]"
Output: "accaccacc"
Explanation: Nested: inner "cc", then "acc" × 3

Constraints