Leetcode #: 394
Name: Decode String
Difficulty: Medium
Url: https://leetcode.com/problems/decode-string/
Prompt
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
Input: s = "3[a2[c]]"
Output: "accaccacc"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].
Approach
The scenarios in which there are no nested values are straightforward. We’ll primarily want to focus on the scenarios in which there are nested values and there are 2 — both of which are displayed below:
1st scenario: "3[a2[c6[d]]]"
2nd scenario: "3[a2[b]5[c]]"
Recursion
These nested brackets represent subproblems, in which you can immediately think of using Recursion as a viable solution. Each level in the Recursion tree would represent how nested a specific subproblem is within their overall subproblem size. As Recursion implements an implicit call stack, this is a good indicator that we can create a Stack to replicate the same behavior and explicitly tell us once we’re done with a subproblem where to pop back up to.
These nested brackets represent subproblems, in which you can immediately think of using Recursion as a viable solution. Each level in the Recursion tree would represent how nested a specific subproblem is within their overall subproblem size. As Recursion implements an implicit call stack, this is a good indicator that we can create a Stack to replicate the same behavior and explicitly tell us once we’re done with a subproblem where to pop back up to.
Explicit Stack
By using an explicit Stack, it’s a LIFO data structure so we know that we should start popping from the Stack once we’ve landed on a closing bracket or ‘]’ We wouldn’t append the closing bracket onto the Stack once we’ve landed on it. We’ll just check every element preceding it as long as the preceding element is not an open bracket or ‘[’. Once we’ve landed on a ‘[’ as we pop from our stack, we have established our substring from ‘[’ and ‘]’ but now we need to calculate what k is for this substring as k determines how many times this substring repeats. We know that k should precede right before the open brackets or ‘[’ so we’ll check each preceding element before the open bracket or ‘[’ and check if it’s a number from 0 to 9. If so, we want to pop that and construct a separate substring that’ll represent k (k can be 2 or even 3 digits, not necessarily 1).
Finally, we can append back to our Stack the substring that we created earlier within our open and closing bracket and repeat it k times as we’ve determined in a separate substring. By repeating this process with all nested brackets or subproblems within our problem size, we’ll eventually have a Stack that is populated with no more open or closing brackets. We can finally join our Stack together into a final concatenated string.
Code
Thank you for reading!
In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.
If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com
