394. 字符串解码

📝 题目描述

给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次（k 是正整数）。 注意：输入字符串总是有效的，无额外空格，且括号格式合法；所有数字只表示重复次数 k（不会出现 3a 或 2[4] 这类输入）。

---

📌 示例

示例 1

输入：

s = "3[a]2[bc]"

输出：

"aaabcbc"

示例 2

输入：

s = "3[a2[c]]"

输出：

"accaccacc"

示例 3

输入：

s = "2[abc]3[cd]ef"

输出：

"abcabccdcdcdef"

示例 4

输入：

s = "abc3[cd]xyz"

输出：

"abccdcdcdxyz"

---

🚀 最优解：双栈法（存字符串+存重复次数）

🔍 思路解析

核心策略：用两个栈分别暂存“之前的字符串”和“重复次数”，遇到括号时完成“暂存-拼接-重复”的逻辑，处理嵌套结构：

1. 初始化工具：
   • strStack：栈，存储“[之前的字符串”；
   • digitStack：栈，存储“[对应的重复次数”；
   • sb：当前拼接的字符串（StringBuilder，避免频繁字符串拼接）；
   • digits：累积多位数字（如“123”需先存为字符串再转整数）；
2. 遍历编码字符串的每个字符：
   • 遇到数字：累积到digits中（处理多位数字，如“12”→“12”）；
   • 遇到[：将当前sb压入strStack、digits转整数压入digitStack，然后重置sb和digits；
   • 遇到]：弹出digitStack的重复次数repeat、弹出strStack的之前字符串preSb，将sb的内容重复repeat次，拼接到preSb后，再把preSb赋值给sb；
   • 遇到字母：直接追加到sb中；
3. 遍历结束后，sb即为解码后的字符串。

---

✅ 完整代码（Java）

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read the encoded string
        String s = scanner.nextLine();

        Solution solution = new Solution();
        String result = solution.decodeString(s);

        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public String decodeString(String s) {
        // 暂存之前的字符串
        Stack<StringBuilder> strStack = new Stack<>();
        // 暂存重复次数
        Stack<Integer> digitStack = new Stack<>();
        // 当前拼接的字符串
        StringBuilder sb = new StringBuilder();
        // 累积多位数字
        StringBuilder digits = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                // 情况1：遇到数字，累积到digits
                digits.append(c);
            } else if (c == '[') {
                // 情况2：遇到[，暂存当前字符串和数字
                strStack.push(sb);
                digitStack.push(Integer.parseInt(digits.toString()));
                // 重置当前字符串和数字
                sb = new StringBuilder();
                digits.setLength(0);
            } else if (c == ']') {
                // 情况3：遇到]，拼接重复后的字符串
                int repeat = digitStack.pop();
                StringBuilder preSb = strStack.pop();
                // 将当前sb重复repeat次，拼接到preSb后
                for (int i = 0; i < repeat; i++) {
                    preSb.append(sb);
                }
                // 更新当前字符串为拼接后的结果
                sb = preSb;
            } else {
                // 情况4：遇到字母，直接追加
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

---

🧠 通俗易懂解释

可以把双栈想象成“暂存箱”，专门处理括号的嵌套逻辑：

• 遇到[：把“当前写了一半的内容”和“要重复的次数”放进暂存箱，然后重新开始写括号里的内容；
• 遇到]：从暂存箱里拿出“之前的内容”和“重复次数”，把括号里写的内容复制n遍，粘到“之前的内容”后面，继续写后续内容。

以示例2 s = "3[a2[c]]" 为例，解码过程像“拆俄罗斯套娃”：

1. 遇到3→digits="3"；
2. 遇到[→把空的sb压入strStack，3压入digitStack，重置sb和digits；
3. 遇到a→sb="a"；
4. 遇到2→digits="2"；
5. 遇到[→把sb="a"压入strStack，2压入digitStack，重置sb和digits；
6. 遇到c→sb="c"；
7. 遇到]→弹出repeat=2、preSb="a"→preSb追加2次c→sb="acc"；
8. 遇到]→弹出repeat=3、preSb=空→preSb追加3次acc→sb="accaccacc"。

---

⏱ 时间复杂度

O(L)

L是解码后字符串的长度，每个字符最终会被拼接/处理一次，无冗余操作。

---

💾 空间复杂度

O(L)

栈的空间（存储暂存的字符串和数字）、sb的空间均不超过解码后字符串的长度L。

---