Decode a Nested Repeat String
Problem
A word is encoded as k[text], which means text repeated k times. Repeats can be nested, and k can have more than one digit. Letters outside brackets stay as they are. Print the decoded word. The input is always valid.
Constraints
- 1 <= length <= 100
- 1 <= k <= 300
- the decoded length is at most 10^5
Examples
Input
3[a2[c]]
Output
accaccacc
Solutions
On [ we save the work so far and start fresh. On ] we repeat the inner text and glue it to the saved text. Each output letter is written a limited number of times, so the time is proportional to the output size.
/*
* Problem : Decode repeats.
* Input : One encoded word.
* Output : The decoded word.
* Approach: Stack.
* Time : O(output)
* Space : O(output)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String solve(String s) {
// Step 1: Two stacks remember the text before each "[" and its repeat count. "current" is the text being built.
java.util.ArrayDeque<StringBuilder> texts = new java.util.ArrayDeque<StringBuilder>();
java.util.ArrayDeque<Integer> counts = new java.util.ArrayDeque<Integer>();
StringBuilder current = new StringBuilder();
int number = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '[') {
// Step 2: Save the state and start a new inner text.
texts.push(current);
counts.push(number);
current = new StringBuilder();
number = 0;
} else if (c == ']') {
// Step 3: Repeat the inner text and add it to the saved outer text.
StringBuilder outer = texts.pop();
int times = counts.pop();
for (int t = 0; t < times; t++) {
outer.append(current);
}
current = outer;
} else {
current.append(c);
}
}
return current.toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.hasNextLine() ? scanner.nextLine() : "";
System.out.println(solve(s));
}
}
Hints (2)
- What do we save at [ ?
- How do we read a number like 12?