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.
1import java.util.Stack;
2
3public class DecodeString {
4 public static String decodeString(String s) {
5 Stack<Integer> countStack = new Stack<>();
6 Stack<String> resultStack = new Stack<>();
7 String result = "";
8 int idx = 0;
9 while (idx < s.length()) {
10 if (Character.isDigit(s.charAt(idx))) {
11 int count = 0;
12 while (Character.isDigit(s.charAt(idx))) {
13 count = 10 * count + (s.charAt(idx) - '0');
14 idx++;
15 }
16 countStack.push(count);
17 } else if (s.charAt(idx) == '[') {
18 resultStack.push(result);
19 result = "";
20 idx++;
21 } else if (s.charAt(idx) == ']') {
22 StringBuilder temp = new StringBuilder(resultStack.pop());
23 int repeatTimes = countStack.pop();
24 while (repeatTimes-- > 0) {
25 temp.append(result);
26 }
27 result = temp.toString();
28 idx++;
29 } else {
30 result += s.charAt(idx++);
31 }
32 }
33 return result;
34 }
35
36 public static void main(String[] args) {
37 String s = "3[a2[c]]";
38 System.out.println(decodeString(s));
39 }
40}This Java solution uses two stacks: one for numbers to handle the multiplicative factor and another for strings to store the current result. The encoded string is parsed character by character, with updates to the current partially decoded string based on characters, '[' or ']', and numbers encountered.
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#include <string>
class Solution {
public:
std::string decodeString(const std::string &s, int &i) {
std::string result = "";
while (i < s.length() && s[i] != ']') {
if (!isdigit(s[i])) {
result += s[i++];
} else {
int n = 0;
while (i < s.length() && isdigit(s[i])) {
n = n * 10 + s[i++] - '0';
}
i++; // skipping the '['
std::string decodedString = decodeString(s, i);
i++; // skipping the ']'
while (n-- > 0) result += decodedString;
}
}
return result;
}
std::string decodeString(const std::string &s) {
int i = 0;
return decodeString(s, i);
}
};
int main() {
Solution sol;
std::string s = "3[a2[c]]";
std::cout << sol.decodeString(s) << std::endl;
return 0;
}In the C++ recursive solution, we employ a helper function that picks up parsing from varying points correlating with where '[' and ']' delimit sequences. The recursion effectively tackles nested cases by delving into deeper levels for fully formed decoded segments that then merge upwards.