vvrf / DSA.log

问题拆解

把 3[a2[c]] 这样的编码串展开成 accaccacc：k[str] 表示方括号里的内容重复 k 次，且允许任意嵌套。

如果没有嵌套，一层循环就能解决：读到数字记倍数，读到 ] 把括号里的串重复拼接。麻烦在嵌套——展开外层之前必须先展开内层，也就是说 ] 的匹配顺序是“后遇到的 [ 先闭合”，这正是栈的后进先出。

关键是想清楚栈里存什么。遇到 [ 时，当前攒了一半的字符串和倍数都要暂停，等内层解码完再回来用，所以把这两样压栈存档：倍数进数字栈，半成品字符串进字符串栈，然后清空工作区从零开始攒内层。遇到 ] 时弹出两者，把“外层半成品 + 内层结果 × 倍数”接成新的当前串。

栈里存的不是括号本身，而是“进入括号前的现场”：外层拼到一半的字符串加上等待生效的倍数，出括号时恢复现场继续拼。

双栈解码

数字可能是多位的（100[ab]），读到数字字符时要用 num = num * 10 + digit 累加，而不是直接当一位数用——这是本题最常见的错。

public String decodeString(String s) {
    Deque<Integer> numStack = new ArrayDeque<>();
    Deque<StringBuilder> strStack = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int num = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0'); // 数字可能多位
        } else if (c == '[') {
            numStack.push(num);   // 存档倍数
            strStack.push(cur);   // 存档外层半成品
            cur = new StringBuilder();
            num = 0;
        } else if (c == ']') {
            int k = numStack.pop();
            StringBuilder outer = strStack.pop();
            outer.append(cur.toString().repeat(k)); // 恢复现场并拼接
            cur = outer;
        } else {
            cur.append(c);
        }
    }
    return cur.toString();
}

def decodeString(s: str) -> str:
    num_stack = []
    str_stack = []
    cur = []  # 用列表攒字符，避免反复拼接字符串
    num = 0
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)  # 数字可能多位
        elif c == "[":
            num_stack.append(num)  # 存档倍数
            str_stack.append(cur)  # 存档外层半成品
            cur = []
            num = 0
        elif c == "]":
            k = num_stack.pop()
            outer = str_stack.pop()
            outer.extend(cur * k)  # 恢复现场并拼接
            cur = outer
        else:
            cur.append(c)
    return "".join(cur)

func decodeString(s string) string {
    var numStack []int
    var strStack []string
    cur := ""
    num := 0
    for _, c := range s {
        switch {
        case c >= '0' && c <= '9':
            num = num*10 + int(c-'0') // 数字可能多位
        case c == '[':
            numStack = append(numStack, num) // 存档倍数
            strStack = append(strStack, cur) // 存档外层半成品
            cur, num = "", 0
        case c == ']':
            k := numStack[len(numStack)-1]
            numStack = numStack[:len(numStack)-1]
            outer := strStack[len(strStack)-1]
            strStack = strStack[:len(strStack)-1]
            cur = outer + strings.Repeat(cur, k) // 恢复现场并拼接
        default:
            cur += string(c)
        }
    }
    return cur
}

pub fn decode_string(s: String) -> String {
    let mut num_stack: Vec<usize> = Vec::new();
    let mut str_stack: Vec<String> = Vec::new();
    let mut cur = String::new();
    let mut num = 0usize;
    for c in s.chars() {
        if c.is_ascii_digit() {
            num = num * 10 + c.to_digit(10).unwrap() as usize; // 数字可能多位
        } else if c == '[' {
            num_stack.push(num);                 // 存档倍数
            str_stack.push(std::mem::take(&mut cur)); // 存档外层半成品
            num = 0;
        } else if c == ']' {
            let k = num_stack.pop().unwrap();
            let mut outer = str_stack.pop().unwrap();
            outer.push_str(&cur.repeat(k)); // 恢复现场并拼接
            cur = outer;
        } else {
            cur.push(c);
        }
    }
    cur
}

走一遍 3[a2[c]]：读 3[a 后，栈里是 (3, "")，工作区 a；读 2[ 时再压 (2, "a")，工作区清空；读 c] 弹出 (2, "a") 得 a + c×2 = acc；再读 ] 弹出 (3, "") 得 acc×3 = accaccacc。每个 ] 只负责闭合最近的 [，嵌套多深都不乱。

这题也可以写成递归下降（遇 [ 递归、遇 ] 返回），本质是把显式栈换成调用栈，思路完全同构；双栈版胜在没有全局下标要维护，出错面更小。

复杂度

指标	复杂度	原因
时间	`O(L)`	L 为输出串长度，每个输出字符被拼接常数次
空间	`O(L)`	栈里存档的半成品总量不超过输出规模

可以迁移的模式

嵌套结构（括号、目录、表达式）配栈是条件反射，栈里存的应该是“进入下一层前的现场”；
解析多位数字用 num = num * 10 + digit 累加，见到非数字字符才算读完；
一对配对符号分别触发“压栈存档”和“弹栈恢复”，中间只管当前层——这套节奏同样适用于基本计算器类题目。

把“现场”从字符串换成运算中间值和符号，就是表达式求值那一族题。