Leetcode 394. 字符串解码：字符串解码的递归与栈两种解法

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。测试用例保证输出的长度不会超过 10^5。

在算法面试中，字符串处理题目总是让人又爱又恨。今天我们要深入剖析的是 LeetCode 第394题——字符串解码。这道题不仅考察了我们对字符串操作的理解，更重要的是考验我们处理嵌套结构的能力。

题目回顾

给定一个编码字符串，格式为 k[encoded_string]，其中 k 是正整数，表示方括号内的字符串要重复 k 次。我们需要将其解码为原始字符串。

示例：

• 输入："3[a]2[bc]"→ 输出："aaabcbc" -输入："3[a2[c]]" → 输出："accaccacc"
• 输入："2[abc]3[cd]ef"→ 输出："abcabccdcdcdef"

解题思路分析

观察题目特点，我们可以发现几个关键点：

1. 嵌套结构：可能存在多层嵌套，如3[a2[c]]
2. 数字只表示重复次数：不会有像 3a 这样的无效输入
3. 需要按顺序处理：从左到右，遇到数字就要记录，遇到 [就要开始处理内部内容

面对这种嵌套结构的问题，我们通常有两种经典解法：

• 递归法：天然适合处理嵌套问题
• 栈法：模拟递归过程，避免函数调用开销

让我们逐一实现这两种方法。

方法一：递归解法

递归的核心思想是：当我们遇到一个数字和左括号时，我们就递归地处理这个括号内的内容。

public class Solution {
   private int index = 0;
   
   public String decodeString(String s) {
      StringBuilder result = new StringBuilder();
       
       while (index < s.length() && s.charAt(index) != ']') {
           if (!Character.isDigit(s.charAt(index))) {
               //如果是普通字符，直接添加
               result.append(s.charAt(index));
              index++;
           } else {
               // 如果是数字，先解析出完整的数字
               int num= 0;
               while(index < s.length()&& Character.isDigit(s.charAt(index))) {
                   num = num * 10 + (s.charAt(index) - '0');
                  index++;
               }
               
              // 跳过'['
               index++;
               
               // 递归处理括号内的内容
               String decoded = decodeString(s);
               
               // 跳过 ']'
               index++;
               
               // 重复指定次数并添加到结果中
               for(int i = 0; i < num; i++) {
                   result.append(decoded);
               }
           }
      }
       
       return result.toString();
   }
}

递归解法的关键点：

• 使用全局变量index 来跟踪当前处理位置
• 当遇到 ] 时，说明当前递归层结束，返回结果
• 数字可能有多位，需要完整解析（如 "12[ab]" 中的 12）

时间复杂度： O(n)，其中 n 是输出字符串的长度

空间复杂度： O(n)，递归调用栈的深度

方法二：栈解法

栈解法的核心思想是维护两个栈：

• 一个栈存储重复次数
• 一个栈存储当前正在构建的字符串

import java.util.*;

public class Solution{
   public String decodeString(String s) {
       Stack<Integer> countStack = new Stack<>();
       Stack<StringBuilder> stringStack = new Stack<>();
       
       StringBuilder currentString = new StringBuilder();
       int currentNum = 0;
       
       for (char c : s.toCharArray()) {
           if (Character.isDigit(c)) {
               //构建完整的数字
              currentNum = currentNum * 10 + (c- '0');
           }else if (c == '[') {
               //遇到左括号，将当前数字和字符串入栈
              countStack.push(currentNum);
               stringStack.push(currentString);
               
               // 重置当前状态
              currentString = new StringBuilder();
               currentNum = 0;
           } else if (c == ']') {
              // 遇到右括号，弹出栈顶进行处理
               StringBuilder decodedString = currentString;
              currentString = stringStack.pop();
               int repeatTimes= countStack.pop();
               
               // 重复指定次数并追加到当前字符串
               for (int i = 0; i < repeatTimes;i++) {
                   currentString.append(decodedString);
               }
           } else {
               //普通字符，直接追加
               currentString.append(c);
           }
       }
       
       return currentString.toString();
   }
}

栈解法的关键点：

• 遇到 [ 时，将当前状态保存到栈中，开始处理新的嵌套层
• 遇到 ]时，完成当前层的处理，将结果合并到上一层
• 使用 StringBuilder提高字符串拼接效率

时间复杂度： O(n)，其中 n 是输出字符串的长度
空间复杂度： O(n)，栈的空间消耗

两种方法对比

实际应用思考

这类字符串解码问题在实际开发中很常见：

• 配置文件解析：处理嵌套的配置结构
• 模板引擎：解析带有循环和条件的模板
• 数据序列化/反序列化：处理嵌套的数据结构

掌握这两种解法不仅能解决这道题，还能帮助我们更好地处理其他涉及嵌套结构的问题。

核心要点：

1. 识别嵌套模式，选择合适的解法
2. 正确处理多位数字的解析
3. 合理管理状态的保存和恢复
4. 注意字符串拼接的性能优化

无论选择哪种方法，关键是要理解问题的本质——这是一个典型的括号匹配+重复展开问题。掌握了这个思路，类似的题目就能迎刃而解了。