P2602. 解压缩算法

解题思路

题意一句话

把形如 {A3B1{C}3}3 的压缩串还原成原始字符串：字符 + 数字 N 表示该字符重复 N 次，{子串} + 数字 N 表示花括号内的内容整体重复 N 次，且花括号支持任意层嵌套。

解法直觉：为什么用栈

本题的难点在「任意嵌套」：展开 {A3B1{C}3}3 时，必须先把最里层的 {C}3 展开成 CCC，再和 A3 → AAA、B1 → B 拼成 AAABCCC，最后整体重复 3 次。这种「先算里层、再回到外层」的结构天然对应栈——每遇到一个 { 就开一层新的"草稿纸"，遇到 } 就把这层草稿展开后拼回上一层。这和 LeetCode 394「字符串解码」是同一个套路，区别只是本题的重复次数写在字符 / 花括号的后面。

步骤

1. 初始化栈 stack = [""]，栈底这个字符串就是最外层（最终答案）。 2. 从左到右扫描压缩串：

• 遇到 {：压入一个空串，表示进入新的一层花括号；
• 遇到 }：读出紧随其后的整段数字 N，弹出栈顶串 seg，把 seg 重复 N 次后拼到新栈顶（上一层）的末尾；
• 遇到普通字符 ch：读出其后的整段数字 N（没有数字按重复 1 次处理），把 ch 重复 N 次拼到栈顶末尾。

3. 扫描结束后，栈底字符串就是解压结果。

以题面例子验证：

• A3 → AAA
• {AB}3 → ABABAB
• {A3B1{C}3}3：内层 A3 → AAA、B1 → B、{C}3 → CCC，拼成 AAABCCC，整体重复 3 次得 AAABCCCAAABCCCAAABCCC。

复杂度

设压缩串长度为 L、解压后字符串长度为 M、最大花括号嵌套深度为 D：

• 时间复杂度：O(L + M × D)。每个输入字符只扫描一次；每一层花括号闭合时会把整段内容复制展开一次，一个输出字符最多被外层花括号再复制 D 次（D 通常很小）。
• 空间复杂度：O(M)。栈中所有字符串的总长度不超过最终输出规模。

坑点提醒

• 重复次数可能是多位数（如 {AB}12），要连续读完整段数字，不能只取一位。
• } 后面的数字属于整个花括号内容，不要误当成花括号内最后一个字符的重复次数。
• 嵌套重复会让输出规模远大于输入（指数放大），Java 拼接务必用 StringBuilder，避免不可变字符串反复复制。

输入输出与边界假设（需人工确认）

题面只给出压缩规则，没有明确输入输出格式和非法输入约定。参考代码按最直接的方式处理：读入一行压缩串，输出一行解压结果；字符或花括号后没有数字时按重复 1 次处理；未对括号不配对等非法输入做特殊约定。若判题用例含异常输入的输出约定，需按真实用例再校准。