字符串解码 图解题解

字符串解码这道题在问什么

输入形如 3[ab2[cd]e] 的编码串，规则是 k[内容] 表示把方括号里的内容重复 k 次，且括号可以任意嵌套，要求还原出展开后的字符串。真正的难点只有一个：嵌套。扫到外层的 3[ab 时里面的 2[cd] 还没解开，外层「重复 3 次」这件事必须先记下来、等内层处理完再兑现。

为什么处理嵌套括号自然想到栈

嵌套括号的闭合顺序是后进先出：最晚打开的括号最先闭合，每个右方括号要匹配的都是最近一个还没闭合的左方括号。「最近打开、最先处理」正是栈的定义，所以括号类解析几乎都以栈为骨架。

关键观察是：任何时刻真正需要动手维护的只有两样东西——当前括号层正在收集的串 cur，和正在逐位攒的倍数 k。至于外层「等会儿要重复几次、展开后接在谁后面」，属于暂时用不上的上下文，遇到左方括号时整体压栈冷冻，等对应的右方括号出现再解冻，恰好不多不少。

两个栈各存什么，压栈后为什么要清空

参考代码用两个栈配合：num_st 存各层的倍数，str_st 存进入各层之前已经拼好的前串。扫描规则四条：遇数字按 k = k * 10 + 当前位累积；遇左方括号把 k 和 cur 分别压栈，然后 cur 清空、k 归零；遇字母直接接到 cur 末尾；遇右方括号执行 cur = str_st.pop() + cur * num_st.pop()。

压栈后必须清空，因为括号内部是一段全新的子串，要从零开始收集，旧的 cur 若不清空会把外层内容错误地卷进重复。而右方括号处的拼接方向也不能反：弹出的前串在前、重复好的括号内容在后，这与它们在原串里的先后位置一致。

为什么一遍扫完结果就是对的

整个算法维持着一条不变量：任何时刻 cur 都是「当前最深那层括号内、已扫过部分的完整展开」，而栈里自底向上依次保存着更外层的半成品和倍数。每闭合一层，就把该层的展开乘上倍数、合并回上一层的半成品，不变量重新成立。扫完全串时所有括号都已闭合、两栈为空，cur 自然就是整串的展开结果，不需要任何补处理。

复杂度怎么算，哪些细节容易错

时间 O(maxK · n)：每个字符可能被外层倍数放大若干倍，n 取输出长度的量级；空间 O(n)，两个栈的深度随嵌套层数增长，cur 随输出增长。

两个高频翻车点：一是倍数可能是多位数，12[a] 里的 12 必须用 k = k * 10 + int(c) 累积，按一位数处理直接出错；二是想省掉一个栈行不通，倍数和前串是两类信息，闭合时要同时取回才能还原「重复几次、接到谁后面」。若偏好递归，可以在每个左方括号处递归解码子串，用调用栈替代显式栈，逻辑完全等价。

Python

def decodeString(s):
    num_st, str_st = [], []
    cur, k = "", 0
    for c in s:
        if c.isdigit():
            k = k * 10 + int(c)
        elif c == "[":
            num_st.append(k); str_st.append(cur)
            cur, k = "", 0
        elif c == "]":
            cur = str_st.pop() + cur * num_st.pop()
        else:
            cur += c
    return cur

C++

string decodeString(string s){
    stack<int> numSt; stack<string> strSt;
    string cur; int k = 0;
    for(char c : s){
        if(isdigit(c)) k = k*10 + (c-'0');
        else if(c=='['){ numSt.push(k); strSt.push(cur); cur=""; k=0; }
        else if(c==']'){
            int rep = numSt.top(); numSt.pop();
            string prev = strSt.top(); strSt.pop();
            string t; while(rep--) t += cur;
            cur = prev + t;
        } else cur += c;
    }
    return cur;
}

Java

String decodeString(String s){
    Deque<Integer> numSt = new ArrayDeque<>();
    Deque<String> strSt = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;
    for(char c : s.toCharArray()){
        if(Character.isDigit(c)) k = k*10 + (c-'0');
        else if(c=='['){
            numSt.push(k); strSt.push(cur.toString());
            cur = new StringBuilder(); k = 0;
        } else if(c==']'){
            int rep = numSt.pop();
            StringBuilder prev = new StringBuilder(strSt.pop());
            for(int i=0;i<rep;i++) prev.append(cur);
            cur = prev;
        } else cur.append(c);
    }
    return cur.toString();
}