Stack· 25 min

Decode String

LeetCode #394 · Medium · Interactive step-by-step visualization

Setup

Example inputs = "3[a2[c]]"
Step 1 / 22

Current step

1 / 22

Keep two stacks. A bracket group must remember both the text built before it and how many times to repeat it. One stack holds pending text, the other holds repeat counts.

Step log

s = "3[a2[c]]"

3
0
[
1
a
2
2
3
[
4
c
5
]
6
]
7

Suspended text · top on right

repeat counts · top on right

building

""

Named pointer
Active node
Committed or completed
Detached or removed
decode-string.java
1public String decodeString(String s) {
2    Deque<String> textStack = new ArrayDeque<>();
3    Deque<Integer> countStack = new ArrayDeque<>();
4    StringBuilder current = new StringBuilder();
5    int repeat = 0;
6    for (char c : s.toCharArray()) {
7        if (Character.isDigit(c)) repeat = repeat * 10 + (c - '0');
8        else if (c == '[') {
9            textStack.push(current.toString());
10            countStack.push(repeat);
11            current = new StringBuilder();
12            repeat = 0;
13        } else if (c == ']') {
14            int times = countStack.pop();
15            current = new StringBuilder(textStack.pop()).append(current.toString().repeat(times));
16        } else current.append(c);
17    }
18    return current.toString();
19}
● Java
Time
O(n × k)
Space
O(n)
Pattern
stack
Frames
22
26 / 75