k[encoded_string] mean that the encoded_string should be repeated k times.
Problem
Given an encoded string s, decode it according to the following rule:k[encoded_string] means that the characters inside the brackets should be repeated k times.
The value of
k is a positive integer, and encoded strings can be nested.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
s = "3[a]2[bc]"Output
"aaabcbc"Example 2
Input
s = "3[a2[c]]"Output
"accaccacc"Solution
This solution uses a Stack to handle the nested encoded strings. We maintain one stack for repetition counts and another stack for the strings that were built before entering a new bracket.When we encounter a digit, we build the repetition count. When we encounter
[, we store the current string and repetition count on their respective stacks and start building a new string. When we encounter ], we retrieve the previous string and repeat the current string according to the stored count.
Normal characters are simply appended to the current string.
class Solution {
public String decodeString(String s) {
Stack<Integer> countStack = new Stack<>();
Stack<String> stringStack = new Stack<>();
String current = "";
int count = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
count = count * 10 + (c - '0');
} else if (c == '[') {
countStack.push(count);
stringStack.push(current);
count = 0;
current = "";
} else if (c == ']') {
int repeat = countStack.pop();
String previous = stringStack.pop();
current = previous + current.repeat(repeat);
} else {
current += c;
}
}
return current;
}
}Complexity
Each character is processed while building the decoded string. The time complexity isO(n) relative to the size of the input and output, where n includes the work required to construct the decoded result.
The stacks store nested strings and repetition counts, so the extra space complexity is
O(n).