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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5char* decodeString(char* s) {
6 int len = strlen(s), num = 0, top = -1, stCap = 100;
7 char* stack = (char*)malloc(stCap * sizeof(char));
8 char** resStack = (char**)malloc(stCap * sizeof(char*));
9 int* numStack = (int*)malloc(stCap * sizeof(int));
10 char* result = (char*)malloc(100 * sizeof(char));
11 int resLen = 0, resCap = 100;
12
13 for (int i = 0; i < len; i++) {
14 if (s[i] >= '0' && s[i] <= '9') {
15 num = num * 10 + (s[i] - '0');
16 } else if (s[i] == '[') {
17 numStack[++top] = num;
18 resStack[top] = (char*)malloc((resCap+1) * sizeof(char));
19 strcpy(resStack[top], result);
20 resLen = 0;
21 num = 0;
22 } else if (s[i] == ']') {
23 char* temp = (char*)malloc((resCap+1) * sizeof(char));
24 strcpy(temp, result);
25 for (int j = 0; j < numStack[top]; j++) {
26 for (int k = 0; k < resLen; k++) {
27 result[resLen * j + k] = temp[k];
28 }
29 }
30 result[resLen * numStack[top]] = '\0';
31 resLen *= numStack[top]; // Update current length
32 sprintf(result, "%s%s", resStack[top--], result); // Add previous result from stack
33 free(temp);
34 } else {
35 result[resLen++] = s[i];
36 if (resLen == resCap) {
37 resCap *= 2;
38 result = (char*)realloc(result, resCap * sizeof(char));
39 }
40 }
41 }
42 return result;
43}
44
45int main() {
46 char s[] = "3[a2[c]]";
47 printf("%s\n", decodeString(s));
48 return 0;
49}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.
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
In this Java solution, recursive strategies parse through the original string input, leveraging a secondary method that iterates when new bracketed sequences arise. Post inner-depth resolutions, the subdivisions are repeated and integrated back into broader levels.