Problem Description
Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
Key Insights
- The encoded string can contain nested patterns, requiring a method to handle recursion or stack-based approaches.
- The digits preceding the brackets indicate how many times the string inside the brackets should be repeated.
- Valid input ensures well-formed brackets and no extraneous characters, simplifying parsing.
Space and Time Complexity
Time Complexity: O(n), where n is the length of the input string. Each character is processed once. Space Complexity: O(n), in the worst case, for the stack or the output string storage.
Solution
To decode the string, we can use a stack to keep track of the current decoded string and the number of times we need to repeat sections of the string. We iterate through each character in the string, and for digits, we build the multiplier; for open brackets, we push the current string and multiplier onto the stack; for closing brackets, we pop from the stack and repeat the string accordingly.