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.
1function decodeString(s) {
2 let numStack = [];
3 let strStack = [];
4 let currentStr = '';
5 let currentNum = 0;
6
7 for (let char of s) {
8 if (!isNaN(char)) {
9 currentNum = currentNum * 10 + Number(char);
10 } else if (char === '[') {
11 numStack.push(currentNum);
12 strStack.push(currentStr);
13 currentStr = '';
14 currentNum = 0;
15 } else if (char === ']') {
16 let repeatTimes = numStack.pop();
17 const lastStr = strStack.pop();
18 currentStr = lastStr + currentStr.repeat(repeatTimes);
19 } else {
20 currentStr += char;
21 }
22 }
23
24 return currentStr;
25}
26
27console.log(decodeString("3[a2[c]]"));The JavaScript solution uses stacks to track numbers and intermediary strings. It builds the final decoded string by iteratively handling characters in accordance with bracket positions, numbers, and plain string elements, affecting the emerging string with repeated and concatenated patterns.
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.
1using System.Text;
class DecodeStringClass {
public static string DecodeString(string s) {
return DecodeHelper(s, new int[] { 0 });
}
private static string DecodeHelper(string s, int[] i) {
StringBuilder result = new StringBuilder();
while (i[0] < s.Length && s[i[0]] != ']') {
if (!Char.IsDigit(s[i[0]])) {
result.Append(s[i[0]]);
i[0]++;
} else {
int num = 0;
while (i[0] < s.Length && Char.IsDigit(s[i[0]])) {
num = num * 10 + s[i[0]] - '0';
i[0]++;
}
i[0]++; // Skip '['
string subResult = DecodeHelper(s, i);
i[0]++; // Skip ']'
while (num-- > 0) {
result.Append(subResult);
}
}
}
return result.ToString();
}
static void Main(string[] args) {
string s = "3[a2[c]]";
Console.WriteLine(DecodeString(s));
}
}This C# solution implements a recursive function which interprets sectioned substrings guided by bounded brackets, where ']' triggers level exits, allowing complex patterns to be gradually expanded and cascaded to form the complete decoded string result.