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 <= 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].This approach uses a stack to decode the string iteratively. Each time we encounter a '[', we push the current accumulated string and the current repetition number to the stack. When we encounter a ']', we pop from the stack, retrieve the last accumulated string and repeat the current decoded substring accordingly.
The C solution uses three stacks: one to store numbers, one to store intermediate results, and one to maintain the current result string. This allows us to handle multiple nesting levels. The solution processes the input string and iteratively constructs the decoded string based on the stack operations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the input string, since we scan through the string linearly while utilizing stack operations.
Space Complexity: O(n), due to the stacks used to keep track of numbers and strings.
This approach uses recursion to decode the string. The function processes the string, and upon encountering a '[', it recursively decodes the repeating substring. This allows elegant handling of nested encoded strings by delegating responsibility to sub-problems.
This C solution employs recursion by making a helper function to progressively decode the input string as it encounters opening brackets for nesting. As we move through the string, closing brackets trigger an upward return in recursion reflecting accumulation and repetition of sub-patterns.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), with n as length of string, since recursive steps are based on string length.
Space Complexity: O(n), mainly for recursive call stack and intermediate storage.
| Approach | Complexity |
|---|---|
| Stack-Based Iterative Decoding | Time Complexity: O(n), where n is the length of the input string, since we scan through the string linearly while utilizing stack operations. |
| Recursive Decoding Approach | Time Complexity: O(n), with n as length of string, since recursive steps are based on string length. |
Encode and Decode Strings - Leetcode 271 - Python • NeetCode • 333,550 views views
Watch 9 more video solutions →Practice Decode String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor