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; 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 won't be input like 3a or 2[4].
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"
Example 4:
Input: s = "abc3[cd]xyz" Output: "abccdcdcdxyz"
Constraints:
1 <= s.length <= 30s consists of lowercase English letters, digits, and square brackets '[]'.s is guaranteed to be a valid input.s are in the range [1, 300].
The description was taken from https://leetcode.com/problems/decode-string/
#O(N) Time, O(N) Spaceclass Solution: def decodeString(self, s: str) -> str: stack = [] for char in s: if char != "]": stack.append(char) else: substring = "" while stack[-1] != "[": substring = stack.pop() + substring stack.pop() n = "" while stack and stack[-1].isnumeric(): n = stack.pop() + n n = int(n) stack.append(n*substring) return "".join(stack)The problem is simple until we start getting the nested brackets.
We can quickly see though, that the inner-most nested strings that we are decoding will need to take precedence over any previous ones. If we define the most nested string as the deepest, we can realize that this problem can be solved with a Depth-First Search.
We could either choose to do this recursively or iteratively, but the iterative version falls more in line with this pattern of strings in problems like the Valid Parenthesis and Backspace String Compare questions.
What we can do is initialize a stack for our DFS and continue adding to it until we have gotten to the first closing bracket. The first closing bracket will belong to the deepest nested string, [ [ [ ] ] ]. When that happens, that deepest string will be on top of the stack so we can decode it by its multiplier which will be directly under it within the stack. Once we have decoded the string, the second deepest string will be on top of the stack and we will repeat this until we have no more strings to decode.
Let's start by initializing our stack.
stack = []
Then, for each character in the string, if it isn't a closing bracket then we will need to continue our DFS and append the character to the stack.
for char in s: if char != "]": stack.append(char)
Let's draw out what this will look like as we go through the code with the test case "3[a2[c]]".
We will continue just appending the character on the stack until we get to the first closing bracket, prior to that, this stack will look like this.
| c |
| [ |
| 2 |
| a |
| [ |
| 3 |
Once we get the first closing bracket, we have found the deepest substring of the current nest. This substring will span up until the first opening bracket. Before we get there, we will continue grabbing the substring characters.
else: substring = "" while stack[-1] != "[": substring = stack.pop() + substring
In this case, the current substring is complete once we pop off the "c".
| [ |
| 2 |
| a |
| [ |
| 3 |
Then, we will pop off the opening bracket that began the substring.
| 2 |
| a |
| [ |
| 3 |
After, we will need the multiplier which will be directly under it. This multiplier can be multiple digits so we will need a loop to keep gathering each digit. We will know when the multiplier ends because the top of the stack will no longer be a number.
n = "" while stack and stack[-1].isnumeric(): n = stack.pop() + n n = int(n)
substring = "c", n = 2.
| a |
| [ |
| 3 |
Once we have the substring we just popped off, and the multiplier, we will combine the two and append it to the stack.
stack.append(n*substring)
| cc |
| a |
| [ |
| 3 |
Once more, we will continue appending characters to the string until we get a closing bracket, which is immediately after in this case, "3[a2[c]]".
We will gather our substring, "acc", pop off the closing bracket, then get the multiplier, three, combine the two and append it back to the stack.
| accaccacc |
Once we are done, we can join the characters in the stack to form a string, then return the string.
return "".join(stack)