Sponsored
Sponsored
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.
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.
1def decode_string(s: str) -> str:
2 stack = []
3 current_str = ''
4 current_num = 0
5
6 for char in s:
7 if char.isdigit():
8 current_num = current_num * 10 + int(char)
9 elif char == '[':
10 stack.append((current_str, current_num))
11 current_str, current_num = '', 0
12 elif char == ']':
13 last_str, num = stack.pop()
14 current_str = last_str + current_str * num
15 else:
16 current_str += char
17
18 return current_str
19
20# Example usage
21s = "3[a2[c]]"
22print(decode_string(s))In this Python solution, a stack is used to maintain state information as we encounter new nested encoding structures. Each digit is multiplier, '[' signals the capturing of a prev state, and ']' denotes expanding the captured state, building the decoded string progressively as either digits or character sequences appear.
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.
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.
1
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.