#394

中等

中频

栈

字符串解码

这是一道围绕字符串展开的高频练习。建议先掌握「栈」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

字符串

原题练习

题目分析

给你一个编码字符串，规则是 k[encoded_string] 表示方括号中的内容要重复 k 次。

而且编码结构可能嵌套，比如 3[a2[c]] 会展开成 accaccacc。

要求你把整个字符串解码出来。

一句话概括：

遇到括号就先保存当前状态，等括号内部处理完，再按重复次数展开。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：遇到 [ 时把当前数字和字符串上下文压栈，遇到 ] 时弹栈并展开当前片段。

推荐代码

推荐解法：栈

时间复杂度： O(n)

空间复杂度： O(n)

核心思路：遇到 [ 时把当前数字和字符串上下文压栈，遇到 ] 时弹栈并展开当前片段。

import java.util.LinkedList;
import java.util.Collections;

class Solution {
    int ptr;

    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;

        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == '[') {
                // 获取一个字母并进栈
                stk.addLast(String.valueOf(s.charAt(ptr++)));
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                // 左括号出栈
                stk.removeLast();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuilder t = new StringBuilder();
                String o = getString(sub);
                // 构造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 将构造好的字符串入栈
                stk.addLast(t.toString());
            }
        }

        return getString(stk);
    }

    public String getDigits(String s) {
        StringBuilder ret = new StringBuilder();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }

    public String getString(LinkedList<String> v) {
        StringBuilder ret = new StringBuilder();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用栈处理嵌套括号，把每一层进入前的上下文保存起来。

核心过程

遇到数字时解析完整重复次数。
遇到 [ 时，把当前字符串和重复次数压栈，并开始新的子串。
遇到普通字母时直接追加到当前字符串。
遇到 ] 时弹栈，把当前子串重复后拼回上一层前缀。

复杂度总结

时间复杂度 O(n)，空间复杂度 O(n)。

面试补一句：这题真正需要管理的不是字符，而是“层级上下文”。

核心思路

字符串解码的难点是嵌套结构。栈最适合保存进入新括号前的上下文：之前的字符串前缀，以及本层要重复的次数。

步骤讲解

先解析连续数字

遇到数字时，要把完整数字解析出来，作为后续括号片段的重复次数。

为什么这样做：重复次数可能不止一位，不能按单个字符处理。

对应代码提示：num = num * 10 + ch - '0';

遇到左括号时压入上下文

把当前字符串和当前重复次数压栈，然后开启新的括号内片段。

为什么这样做：进入更深层嵌套前，必须保存上一层上下文。

对应代码提示：countStack.push(num); stringStack.push(current.toString());

遇到右括号时弹栈展开

弹出重复次数和前缀字符串，把当前片段重复指定次数后拼回前缀。

为什么这样做：右括号意味着当前层结束，要把子结果合并回上一层。

对应代码提示：current = new StringBuilder(prev).append(segment.repeat(count));

易错点

数字只按一位处理

像 12[a] 会被错误拆成两次重复。

正确理解：遇到数字时持续累乘累加，解析完整整数。

进入新层时没清空当前状态

新括号层会继承上一层内容，结果串联错误。

正确理解：压栈后把当前字符串和计数器重置。

嵌套结构靠递归但状态定义不清

容易把括号层级和重复次数缠在一起写乱。

正确理解：优先用栈把“前缀字符串”和“重复次数”两个上下文拆开保存。

复杂度与适用判断

时间复杂度：O(n)

空间复杂度：O(n)

比其他方案更好在哪里：比手写递归下降更直接，也更容易在面试里稳住嵌套层级状态。

适用判断：字符串题里只要出现嵌套结构和进入/退出上下文，优先考虑栈。

额外提醒

压栈时保存的是“进入括号前的世界”，不是只保存当前片段。

其他语言 / 其他解法

递归法

递归方法的核心思路是使用指针遍历字符串，遇到字母则直接添加到结果中；遇到数字则解析完整数字作为重复次数，然后跳过左括号，递归解析括号内的字符串，最后将递归结果重复指定次数后添加到结果中；遇到右括号则结束当前递归层并返回结果。递归终止条件是指针到达字符串末尾或遇到右括号。通过这种方式，可以自然处理嵌套的括号结构。

时间复杂度：O(n)

空间复杂度：O(n)

一句话思路：递归方法的核心思路是使用指针遍历字符串，遇到字母则直接添加到结果中；遇到数字则解析完整数字作为重复次数，然后跳过左括号，递归解析括号内的字符串，最后将递归结果重复指定次数后添加到结果中；遇到右括号则结束当前递归层并返回结果。递归终止条件是指针到达字符串末尾或遇到右括号。通过这种方式，可以自然处理嵌套的括号结构。

class Solution {
    String src;
    int ptr;

    public String decodeString(String s) {
        src = s;
        ptr = 0;
        return getString();
    }

    public String getString() {
        if (ptr == src.length() || src.charAt(ptr) == ']') {
            // 递归终止条件
            return "";
        }

        char cur = src.charAt(ptr);
        int repTime = 1;
        String ret = "";

        if (Character.isDigit(cur)) {
            // 解析数字
            repTime = getDigits();
            // 过滤左括号
            ++ptr;
            // 递归解析括号内的字符串
            String str = getString();
            // 过滤右括号
            ++ptr;
            // 构造字符串
            while (repTime-- > 0) {
                ret += str;
            }
        } else if (Character.isLetter(cur)) {
            // 解析字母
            ret = String.valueOf(src.charAt(ptr++));
        }

        // 继续解析剩余部分
        return ret + getString();
    }

    public int getDigits() {
        int ret = 0;
        while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
            ret = ret * 10 + (src.charAt(ptr++) - '0');
        }
        return ret;
    }
}

动画演示

如果你还没完全看懂，可以展开动画演示。

栈动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

输入字符串:

准备就绪 - 输入字符串，然后点击开始

递归法动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

输入字符串:

准备就绪 - 输入字符串，然后点击开始

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。