394. 字符串解码#

今天我们来探讨一道非常有趣的算法题 - LeetCode 394「字符串解码」。这道题考察了栈和递归的灵活运用，是一道非常能锻炼编程思维的好题目。

📚 从生活场景理解#

想象你正在开发一个文本压缩软件。比如要表达”hellohellobello”，与其写三遍，我们可以写成”3[hello]“来节省空间。如果字符串中还包含重复的部分，可以继续嵌套压缩，这就是今天要解决的问题！

问题描述#

题目目标#

给定一个经过编码的字符串 s ，按照规则 k[encoded_string] 进行解码并返回结果，其中方括号内的字符串会被重复 k 次。输入保证格式合法，且不会出现额外空格。

示例 1#

输入： s = "3[a]2[bc]" 输出： "aaabcbc" 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 问题解析#

题目要求：给定一个经过编码的字符串，返回它解码后的字符串。编码规则是：

k[encoded_string] 表示 encoded_string 重复 k 次
encoded_string 里可能包含更多的方括号结构
数字 k 保证为正整数

示例：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

java

🤔 思维发展历程#

1. 初学者思路#

可能会想到用简单的字符串替换。但遇到嵌套结构时（如”3[a2[c]]”），这种方法就难以处理了。

2. 栈的思路#

利用栈来处理嵌套结构，遇到’]‘时弹出栈内元素直到遇到’[‘，处理这一层的重复。

3. 递归思路#

将问题分解为子问题：每遇到一个’[‘就是一个新的子问题的开始，遇到对应的’]‘就是子问题的结束。

🚀 优雅的递归解决方案#

class Solution {
    // 全局游标：在递归层之间共享当前位置，避免每层都切子串
    private int index = 0;

    public String decodeString(String s) {
        // 当前递归层负责构建的一段解码结果
        StringBuilder result = new StringBuilder();

        // 只要没走到字符串末尾，就持续解析
        while (index < s.length()) {
            // 读取当前游标指向的字符
            char currentChar = s.charAt(index);

            // 分支1：遇到数字，表示接下来是 k[...] 结构
            if (Character.isDigit(currentChar)) {
                // 解析完整重复次数（可能是多位数，如 12[a]）
                int count = 0;
                while (Character.isDigit(s.charAt(index))) {
                    // 十进制累积：例如 '1' -> 1, 再读 '2' -> 12
                    count = count * 10 + (s.charAt(index) - '0');
                    // 游标右移，继续读下一位
                    index++;
                }

                // 当前字符应为 '['，跳过它，进入括号内部内容
                index++;

                // 递归解析子串：直到遇到与本层匹配的 ']'
                String decodedString = decodeString(s);

                // 将子串重复 count 次追加到当前层结果中
                while (count > 0) {
                    result.append(decodedString);
                    count--;
                }

            // 分支2：普通字母，直接拼接到当前层结果
            } else if (Character.isLetter(currentChar)) {
                // 追加当前字母
                result.append(currentChar);
                // 消费掉该字符，继续向后解析
                index++;

            // 分支3：遇到右括号，说明当前递归层结束
            } else if (currentChar == ']') {
                // 跳过 ']'
                index++;
                // 返回本层已构建完成的结果给上一层
                return result.toString();

            }
        }

        // 走到字符串末尾（最外层常见），返回当前层结果
        return result.toString();
    }
}

java

📝 代码详解#

让我们深入理解这个递归解决方案的精妙之处：

1. 全局索引设计#

使用全局索引来追踪当前处理的字符位置，这样可以在递归调用间共享处理进度。

2. 状态处理#

代码处理三种主要状态：

遇到数字：收集完整数字，然后递归处理方括号内的内容
遇到字母：直接添加到结果中
遇到’]‘：表示当前层级处理完成，返回结果

3. 数字处理#

考虑到数字可能是多位数，使用循环来获取完整的数字值：

// 当前片段演示如何解析多位数字（例如 "123[a]" 中的 123）
int count = 0;
while (Character.isDigit(s.charAt(index))) {
    // 十进制累加：先左移一位（*10），再加当前数位
    count = count * 10 + (s.charAt(index) - '0');
    // 游标右移，读取下一位数字
    index++;
}

java

4. 递归精髓#

每次遇到’[‘就会触发一次递归调用，处理括号内的内容。递归函数返回时，正好处理完一对括号内的内容。

🎯 易错点剖析#

数字处理
- 别忘了处理多位数字
- 注意数字到字符的转换
嵌套处理
- 正确处理嵌套的括号结构
- 保持对递归层级的清晰理解
索引管理
- 准确移动和更新索引位置
- 处理边界情况

💡 举一反三#

这种解码思想可以应用到多种场景：

HTML解析
- 处理嵌套的HTML标签结构
- 构建DOM树
表达式求值
- 处理带括号的数学表达式
- 计算器的实现
文件压缩
- 实现简单的文本压缩算法
- 处理重复模式

🎨 图解演示#

<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="800" height="400" fill="#f8f9fa"/>

  <!-- 标题 -->
  <text x="50" y="40" font-size="20" fill="#1976d2">字符串解码递归过程</text>

  <!-- 输入字符串显示 -->
  <g transform="translate(50,80)">
    <text x="0" y="0" font-size="16">输入：3[a2[c]]</text>

    <!-- 字符框 -->
    <g transform="translate(0,20)">
      <rect x="0" y="0" width="40" height="40" fill="#e3f2fd" stroke="#1976d2"/>
      <text x="20" y="25" text-anchor="middle">3</text>

      <rect x="40" y="0" width="40" height="40" fill="#e3f2fd" stroke="#1976d2"/>
      <text x="60" y="25" text-anchor="middle">[</text>

      <rect x="80" y="0" width="40" height="40" fill="#e3f2fd" stroke="#1976d2"/>
      <text x="100" y="25" text-anchor="middle">a</text>

      <rect x="120" y="0" width="40" height="40" fill="#e3f2fd" stroke="#1976d2"/>
      <text x="140" y="25" text-anchor="middle">2</text>

      <rect x="160" y="0" width="40" height="40" fill="#e3f2fd" stroke="#1976d2"/>
      <text x="180" y="25" text-anchor="middle">[</text>

      <rect x="200" y="0" width="40" height="40" fill="#e3f2fd" stroke="#1976d2"/>
      <text x="220" y="25" text-anchor="middle">c</text>

      <rect x="240" y="0" width="40" height="40" fill="#e3f2fd" stroke="#1976d2"/>
      <text x="260" y="25" text-anchor="middle">]</text>

      <rect x="280" y="0" width="40" height="40" fill="#e3f2fd" stroke="#1976d2"/>
      <text x="300" y="25" text-anchor="middle">]</text>
    </g>
  </g>

  <!-- 递归树 -->
  <g transform="translate(50,180)">
    <text x="0" y="0" font-size="16">递归解析过程：</text>

    <!-- 第一层 -->
    <circle cx="200" cy="40" r="30" fill="#c8e6c9" stroke="#388e3c"/>
    <text x="200" y="45" text-anchor="middle">3[...]</text>

    <!-- 连接线 -->
    <line x1="200" y1="70" x2="200" y2="100" stroke="#388e3c" stroke-width="2"/>

    <!-- 第二层 -->
    <circle cx="200" cy="130" r="30" fill="#bbdefb" stroke="#1976d2"/>
    <text x="200" y="135" text-anchor="middle">2[c]</text>

    <!-- 结果显示 -->
    <g transform="translate(350,40)">
      <text x="0" y="0" font-size="14">解析步骤：</text>
      <text x="0" y="30" font-size="14">1. 外层：3[a2[c]]</text>
      <text x="0" y="60" font-size="14">2. 内层：2[c] → cc</text>
      <text x="0" y="90" font-size="14">3. 组合：a+cc → acc</text>
      <text x="0" y="120" font-size="14">4. 重复：acc×3 → accaccacc</text>
    </g>
  </g>
</svg>

plaintext

🌟 面试技巧#

思路说明
- 先解释为什么选择递归方案
- 说明递归终止条件和状态传递
复杂度分析
- 时间复杂度：O(n)，其中n是解码后的字符串长度
- 空间复杂度：O(n)，递归调用栈的深度
优化讨论
- 可以讨论迭代方案的实现
- 考虑内存优化的可能性

🎩 栈解法版本#

除了递归，我们还可以用栈来解决这个问题：

class Solution {
    public String decodeString(String s) {
        // 计数栈：保存每一层 '[' 对应的重复次数 k
        Stack<Integer> countStack = new Stack<>();
        // 字符串栈：保存进入新层前的“外层已构建字符串”
        Stack<StringBuilder> stringStack = new Stack<>();
        // 当前层正在构建的字符串
        StringBuilder currentString = new StringBuilder();
        // 当前正在解析的数字（重复次数），支持多位数
        int count = 0;

        // 逐字符遍历编码串
        for (char ch : s.toCharArray()) {
            // 1) 数字：累计重复次数
            if (Character.isDigit(ch)) {
                count = count * 10 + (ch - '0');
            // 2) 左括号：进入新层，先保存现场
            } else if (ch == '[') {
                // 保存本层重复次数
                countStack.push(count);
                // 保存进入新层前已经构建好的字符串
                stringStack.push(currentString);
                // 开始构建新层字符串
                currentString = new StringBuilder();
                // count 清零，准备读取后续可能出现的新数字
                count = 0;
            // 3) 右括号：当前层结束，回到上一层并执行重复拼接
            } else if (ch == ']') {
                // 当前层完整解码结果
                StringBuilder decodedString = currentString;
                // 恢复上一层字符串
                currentString = stringStack.pop();
                // 取出当前层对应的重复次数
                int repeatTimes = countStack.pop();
                // 将当前层结果重复追加到上一层
                while (repeatTimes-- > 0) {
                    currentString.append(decodedString);
                }
            // 4) 普通字母：直接追加到当前层
            } else {
                currentString.append(ch);
            }
        }

        // 遍历完成后，currentString 就是最终解码结果
        return currentString.toString();
    }
}

java

这个栈解法的优点是：

避免了递归调用的开销
更容易理解状态的变化过程
适合处理超大规模的输入

这道题展示了如何优雅地处理嵌套结构，无论是使用递归还是栈，都体现了解决复杂问题的不同思维方式。如果你对这个问题还有任何疑问，欢迎在评论区讨论！