Decode a Nested Repeat String

medium Strings

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

Best approachTime O(output)Space O(output)

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.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * 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)
  1. What do we save at [ ?
  2. How do we read a number like 12?