Back to DSA

Decode String

medium
Acceptance: 49%
StackStringRecursion

Decode a string that has been encoded with the pattern k[substring], where k is a positive integer and substring is the text to be repeated k times. Brackets may be nested. Assume the input is always syntactically correct with no extraneous spaces.

Examples

Example 1:
Input:s = "2[xy]3[z]"
Output:"xyxyzzzz"
Example 2:
Input:s = "2[a3[b]]"
Output:"abbbabbb"

Hints

Related Problems

Min StackmediumValid ParentheseseasyEvaluate Reverse Polish NotationmediumDaily TemperaturesmediumNext Greater Element Ieasy
00:00
import java.util.*;

class Solution {
    public String decodeString(String s) {
        Deque<String> strStack = new ArrayDeque<>();
        Deque<Integer> numStack = new ArrayDeque<>();
        StringBuilder curr = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                numStack.push(num);
                strStack.push(curr.toString());
                curr = new StringBuilder();
                num = 0;
            } else if (c == ']') {
                int repeat = numStack.pop();
                StringBuilder temp = new StringBuilder(strStack.pop());
                for (int i = 0; i < repeat; i++) temp.append(curr);
                curr = temp;
            } else {
                curr.append(c);
            }
        }
        return curr.toString();
    }
}
Time complexityO(n * maxK)
Space complexityO(n)