忍者算法

Appearance

字符串解码：优雅处理嵌套结构的递归艺术！ ​

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

📚 从生活场景理解 ​

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

💡 问题解析 ​

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

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

示例：

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

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

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

🤔 思维发展历程 ​

1. 初学者思路 ​

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

2. 栈的思路 ​

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

3. 递归思路 ​

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

🚀 优雅的递归解决方案 ​

java
class Solution {
    private int index = 0;  // 全局索引，用于遍历字符串
    
    public String decodeString(String s) {
        StringBuilder result = new StringBuilder();
        
        while (index < s.length()) {
            char currentChar = s.charAt(index);
            
            if (Character.isDigit(currentChar)) {
                // 处理数字：获取完整的数字值
                int count = 0;
                while (Character.isDigit(s.charAt(index))) {
                    count = count * 10 + (s.charAt(index) - '0');
                    index++;
                }
                
                // 跳过'['
                index++;
                
                // 递归处理括号内的内容
                String decodedString = decodeString(s);
                
                // 重复count次
                while (count > 0) {
                    result.append(decodedString);
                    count--;
                }
                
            } else if (Character.isLetter(currentChar)) {
                // 处理字母：直接添加到结果中
                result.append(currentChar);
                index++;
                
            } else if (currentChar == ']') {
                // 遇到']'：当前层级的解码完成
                index++;
                return result.toString();
                
            }
        }
        
        return result.toString();
    }
}

📝 代码详解 ​

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

1. 全局索引设计 ​

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

2. 状态处理 ​

代码处理三种主要状态：

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

3. 数字处理 ​

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

java
int count = 0;
while (Character.isDigit(s.charAt(index))) {
    count = count * 10 + (s.charAt(index) - '0');
    index++;
}

4. 递归精髓 ​

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

🎯 易错点剖析 ​

  1. 数字处理

    • 别忘了处理多位数字
    • 注意数字到字符的转换

  2. 嵌套处理

    • 正确处理嵌套的括号结构
    • 保持对递归层级的清晰理解

  3. 索引管理

    • 准确移动和更新索引位置
    • 处理边界情况

💡 举一反三 ​

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

  1. HTML解析

    • 处理嵌套的HTML标签结构
    • 构建DOM树

  2. 表达式求值

    • 处理带括号的数学表达式
    • 计算器的实现

  3. 文件压缩

    • 实现简单的文本压缩算法
    • 处理重复模式

🎨 图解演示 ​

svg
<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>

🌟 面试技巧 ​

  1. 思路说明

    • 先解释为什么选择递归方案
    • 说明递归终止条件和状态传递

  2. 复杂度分析

    • 时间复杂度：O(n)，其中n是解码后的字符串长度
    • 空间复杂度：O(n)，递归调用栈的深度

  3. 优化讨论

    • 可以讨论迭代方案的实现
    • 考虑内存优化的可能性

🎩 栈解法版本 ​

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

java
class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int count = 0;
        
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                count = count * 10 + (ch - '0');
            } else if (ch == '[') {
                countStack.push(count);
                stringStack.push(currentString);
                currentString = new StringBuilder();
                count = 0;
            } else if (ch == ']') {
                StringBuilder decodedString = currentString;
                currentString = stringStack.pop();
                int repeatTimes = countStack.pop();
                while (repeatTimes-- > 0) {
                    currentString.append(decodedString);
                }
            } else {
                currentString.append(ch);
            }
        }
        
        return currentString.toString();
    }
}

这个栈解法的优点是：

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

作者：忍者算法 公众号：忍者算法 🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步 #算法面试 #LeetCode #递归 #栈

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