Decode String

Problem

Decode an encoded string. The encoding rule is k[encoded_string] — the encoded_string inside the brackets is repeated exactly k times. Rules: - k is always a positive integer and can be multi-digit (e.g. 100[a]). - encoded_string may itself contain more k[...] groups — brackets nest (e.g. 3[a2[c]]). - Plain letters can appear with no brackets around them; they decode to themselves. - The input is always well-formed — every [ has a matching ] and is preceded by a number. Return the fully decoded string.

Constraints

• 1 ≤ s.length ≤ 30
• 1 ≤ k ≤ 300

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def decodeString(self, s):
        stack = [['', 1]]
        num = ''
        for ch in s:
            if ch.isdigit():
                num += ch
            elif ch == '[':
                stack.append(['', int(num)]); num = ''
            elif ch == ']':
                seg, k = stack.pop()
                stack[-1][0] += seg * k
            else:
                stack[-1][0] += ch
        return stack[0][0]

Java

import java.util.Stack;

class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int k = 0;
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                k = k * 10 + ch - '0';
            } else if (ch == '[') {
                // push the number k to countStack
                countStack.push(k);
                // push the currentString to stringStack
                stringStack.push(currentString);
                // reset currentString and k
                currentString = new StringBuilder();
                k = 0;
            } else if (ch == ']') {
                StringBuilder decodedString = stringStack.pop();
                // decode currentK[currentString] by appending currentString k times
                for (int currentK = countStack.pop(); currentK > 0; currentK--) {
                    decodedString.append(currentString);
                }
                currentString = decodedString;
            } else {
                currentString.append(ch);
            }
        }
        return currentString.toString();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.