栈与队列中等1 种解法

#394字符串解码

将 k[encoded_string] 按重复次数展开，编码可以嵌套且 k 可以有多位。

#字符串#栈#递归

解题主线

遇到左括号时保存外层结果与重复次数，并为括号内片段开启新的 StringBuilder。

遇到右括号时完成当前层展开，再拼接回上一层，天然支持嵌套结构。

读取数字时用 repeat = repeat × 10 + digit 累积多位次数。

解法 1：双栈迭代解码

次数栈保存每层 k，字符串栈保存进入括号前的前缀；闭括号时展开当前层并恢复外层。

时间复杂度

O(N + L)，N 为编码串长度，L 为解码后字符串长度

空间复杂度

O(N + L)，用于层级栈与构造中的输出字符

394. 字符串解码 · 双栈迭代解码

java

import java.util.ArrayDeque;
import java.util.Deque;

final class Solution {
    public String decodeString(String s) {
        Deque<Integer> repeats = new ArrayDeque<>();
        Deque<StringBuilder> prefixes = new ArrayDeque<>();
        StringBuilder current = new StringBuilder();
        int repeat = 0;

        for (int i = 0; i < s.length(); i++) {
            char character = s.charAt(i);
            if (Character.isDigit(character)) {
                repeat = repeat * 10 + character - '0';
            } else if (character == '[') {
                repeats.push(repeat);
                prefixes.push(current);
                repeat = 0;
                current = new StringBuilder();
            } else if (character == ']') {
                int times = repeats.pop();
                StringBuilder expanded = prefixes.pop();
                expanded.append(current.toString().repeat(times));
                current = expanded;
            } else {
                current.append(character);
            }
        }
        return current.toString();
    }
}

次数栈保存每层 k，字符串栈保存进入括号前的前缀；闭括号时展开当前层并恢复外层。

String.repeat 自 Java 11 起可用，Java 21 环境可直接使用。

边界与易错点

不能把每个数字字符当成独立重复次数，例如 12[a] 的次数是 12。
两个栈必须同步入栈和出栈，分别恢复上一层次数与字符串。
遗留 Stack 可用 ArrayDeque 替代。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q394_stack_decodeString.java