Decode String
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.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 105.
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Constraints:
1 <= s.length <= 30sconsists of lowercase English letters, digits, and square brackets'[]'.sis guaranteed to be a valid input.- All the integers in
sare in the range[1, 300].
Solve it on LeetCode
Approaches
1. Recursive Approach
Intuition:
In this approach, we use recursion to decode the string. The idea is to iterate through the string and whenever an opening bracket '[' is encountered, we recursively decode the string within the brackets and repeat it the specified number of times. This is tracked via a counter. Each recursive call handles a part of the string enclosed in square brackets.
Steps:
- Initialize a global index to track the position in the string.
- Iterate over the string and for each character:
- If it's a digit, build the multiplier (k=2 or 12, etc.).
- If it's '[', recursively decode the substring that follows.
- If it’s ']', return the accumulated string up to this point.
- If it's a letter, append it to the result string.
- This approach is accomplished by a helper method that performs the recursion and returns the decoded substring.
Code:
- Time Complexity: O(n), where n is the length of the string. Each character is processed once.
- Space Complexity: O(n), used for the recursion stack and output string.
2. Iterative Approach using Stacks
Intuition:
Instead of using recursion, you can use stacks to simulate the process. Use two stacks: one to store numbers (multiplier) and another to store current encoded string segments. Traverse through the string, upon encountering '[', push the current result and multiplier onto the stacks and reset them. When ']' is encountered, pop from the stacks to get the last string and multiplier, concatenate the result.
Steps:
- Traverse through the input string and perform the following:
- If a number is found, compute the full number (multiplier) using a loop.
- If '[', push the current string and multiplier on stacks.
- If ']', pop from the stacks and append the current string.
- If it's a character, append it to the current result string.
- Concatenate results as needed upon encountering ']' and continue until end.
Code:
- Time Complexity: O(n), where n is the length of the string. Each character is processed once.
- Space Complexity: O(n), for the stacks and output string.