Stack
Decode String
DESCRIPTION (inspired by Leetcode.com)
Given an encoded string s, write a function to return its decoded string.
The encoding rule is k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. k is always a positive integer, and the brackets can be nested.
You can assume the input is always well-formed: there are no extra spaces, every square bracket is properly matched, and digits only ever appear to specify a repeat count k (so you won't see input like 3a or 2[4]).
Constraints:
- 1 <= s.length
- s consists of lowercase English letters, digits, and the square brackets [ and ].
- All repeat counts k are positive integers and may have more than one digit (for example, 10[a]).
- The input string is guaranteed to be valid.
Example 1:
Inputs:
s = "3[a]2[bc]"
Output:
"aaabcbc"
(Explanation: 3[a] decodes to "aaa" and 2[bc] decodes to "bcbc".)
Example 2:
Inputs:
s = "3[a2[c]]"
Output:
"accaccacc"
(Explanation: the inner 2[c] becomes "cc", so a2[c] is "acc", which is then repeated 3 times.)
Example 3:
Inputs:
s = "2[abc]3[cd]ef"
Output:
"abcabccdcdcdef"
public class Solution {
public String decodeString(String s) {
// Your code goes here
}
}Run your code to see results here
Have suggestions or found something wrong?
Explanation
We start by initializing our stack, and the variables curr_string and current_number. The stack allows us to account for nested sequences correctly. curr_string represents the current string we currently decoding, and current_number represents the number of times we need to repeat it when the current decode sequence is completed (i.e. when we encounter a closing "]" bracket).
public String decodeString(String s) {Stack<String> stringStack = new Stack<>();Stack<Integer> numberStack = new Stack<>();String currString = "";int currentNumber = 0;for (char c : s.toCharArray()) {if (c == '[') {stringStack.push(currString);numberStack.push(currentNumber);currString = "";currentNumber = 0;} else if (c == ']') {int num = numberStack.pop();String prevString = stringStack.pop();currString = prevString + currString.repeat(num);} else if (Character.isDigit(c)) {currentNumber = currentNumber * 10 + (c - '0');} else {currString += c;}}return currString;}
decode string
0 / 1
We then iterate over each character in the encoded string, handling each character as follows:
"[": Start of a new sequence
When we encounter an opening bracket, we push the current string curr_string and the current number current_number to the stack and reset curr_string to an empty string and current_number to 0. These values that we pushed onto the stack represent the "context" of the current sequence we are decoding. We use current_number to keep track of the number of times we need to repeat the current string we are about to decode, while curr_string represents the value of the string that will be prepended to the result of the current sequence.
public String decodeString(String s) {Stack<String> stringStack = new Stack<>();Stack<Integer> numberStack = new Stack<>();String currString = "";int currentNumber = 0;for (char c : s.toCharArray()) {if (c == '[') {stringStack.push(currString);numberStack.push(currentNumber);currString = "";currentNumber = 0;} else if (c == ']') {int num = numberStack.pop();String prevString = stringStack.pop();currString = prevString + currString.repeat(num);} else if (Character.isDigit(c)) {currentNumber = currentNumber * 10 + (c - '0');} else {currString += c;}}return currString;}
[
0 / 2
"]": End of a sequence
When we encounter a closing bracket, we pop the top two values off the stack: first the repeat count we saved on the way in, then the previous string. We repeat curr_string by that count, prepend the previous string, and the result becomes our new curr_string.
public String decodeString(String s) {Stack<String> stringStack = new Stack<>();Stack<Integer> numberStack = new Stack<>();String currString = "";int currentNumber = 0;for (char c : s.toCharArray()) {if (c == '[') {stringStack.push(currString);numberStack.push(currentNumber);currString = "";currentNumber = 0;} else if (c == ']') {int num = numberStack.pop();String prevString = stringStack.pop();currString = prevString + currString.repeat(num);} else if (Character.isDigit(c)) {currentNumber = currentNumber * 10 + (c - '0');} else {currString += c;}}return currString;}
]
0 / 1
Digit
When char is a digit, we update current_number by multiplying it by 10 and adding the value of the digit. current_number is used to keep track of the number of times we need to repeat the current string we are just about to decode.
public String decodeString(String s) {Stack<String> stringStack = new Stack<>();Stack<Integer> numberStack = new Stack<>();String currString = "";int currentNumber = 0;for (char c : s.toCharArray()) {if (c == '[') {stringStack.push(currString);numberStack.push(currentNumber);currString = "";currentNumber = 0;} else if (c == ']') {int num = numberStack.pop();String prevString = stringStack.pop();currString = prevString + currString.repeat(num);} else if (Character.isDigit(c)) {currentNumber = currentNumber * 10 + (c - '0');} else {currString += c;}}return currString;}
initialize variables
0 / 2
Letter
When we encounter a letter, we append it to the current string curr_string.
Solution
public String decodeString(String s) {Stack<String> stringStack = new Stack<>();Stack<Integer> numberStack = new Stack<>();String currString = "";int currentNumber = 0;for (char c : s.toCharArray()) {if (c == '[') {stringStack.push(currString);numberStack.push(currentNumber);currString = "";currentNumber = 0;} else if (c == ']') {int num = numberStack.pop();String prevString = stringStack.pop();currString = prevString + currString.repeat(num);} else if (Character.isDigit(c)) {currentNumber = currentNumber * 10 + (c - '0');} else {currString += c;}}return currString;}
decode string
0 / 20
Complexity Analysis
For this problem, let n be the length of the input string and S be the length of the decoded output string.
What is the time complexity of this solution?
O(4ⁿ)
O(n³)
O(1)
O(S)