22-Decode-String.md

Decode String

Problem Link

https://leetcode.com/problems/decode-string/

---

Pattern

• Stack
• String

---

Approach

Use stacks for counts and partial strings to handle nested encoded segments.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public String decodeString(String s) {
        Stack<Integer> counts = new Stack<>();
        Stack<StringBuilder> strings = new Stack<>();
        StringBuilder curr = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                counts.push(num);
                strings.push(curr);
                curr = new StringBuilder();
                num = 0;
            } else if (c == ']') {
                int count = counts.pop();
                StringBuilder prev = strings.pop();
                for (int i = 0; i < count; i++) prev.append(curr);
                curr = prev;
            } else {
                curr.append(c);
            }
        }
        return curr.toString();
    }
}