Decode an Encoded String
Given a string encoded according to a specific pattern, decode it to retrieve the original message. The encoding pattern involves wrapping a repeated segment of the string in a prefix which indicates how many times the segment should occur. The repeated segment of the string is always enclosed within square brackets [ ]. More than one segment of the string can be encoded and nested encodings are possible.
[ "3[a]" ]
Explanation. The segment 'a' is repeated 3 times.
[ "2[abc]3[cd]ef" ]
Explanation. The segment 'abc' is repeated 2 times and 'cd' is repeated 3 times. Then the characters 'ef' follows as they are.
[ "3[a2[c]]" ]
Explanation. The segment 'c' is repeated 2 times inside the repeating segment of 'a', and then 'a' along with its nested 'cc' is repeated 3 times.
[ "2[b4[F]c]" ]
Explanation. The characters 'b' and 'c' encapsulate a repeated segment 'F' 4 times, and this complete pattern 'bFFFFc' itself repeats twice.
Follow-up: Can the algorithm be optimized to handle very deep nesting by using non-recursive techniques?
The input string will always be valid and non-empty, conforming to the given encoding pattern. The input string's length won't exceed 1000 characters.
- Accepted
- 1/1
- Acceptance Rate
- 100.0%
- Views
- 24