Medium

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，数字只表示重复的次数 k，例如不会出现像 3a 或 2[4] 的输入。

生成的测试用例满足解码字符串的长度不会超过 10^5。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个有效的输入
  • s 中所有整数的取值范围为 [1, 300]

解题思路

这是一个经典的栈问题，需要处理嵌套的括号结构。主要有两种解法：栈解法和递归解法。

栈解法（推荐）

核心思想是使用两个栈分别保存数字和字符串：

  1. 遍历字符串，遇到数字时累积计算（可能是多位数）
  2. 遇到 [ 时，将当前数字和字符串分别压入栈中，重置当前状态
  3. 遇到 ] 时，弹出栈顶的数字和字符串，将当前字符串重复指定次数后与弹出的字符串拼接
  4. 遇到字母时直接拼接到当前字符串

这种方法能够很好地处理嵌套结构，时间复杂度为 O(n)，其中 n 是结果字符串的长度。

递归解法

递归解法的思路是将问题分解为子问题，每次遇到 [ 就递归处理括号内的内容。虽然代码更简洁，但需要额外的递归栈空间。

两种方法的时间复杂度相同，但栈解法的空间复杂度相对更可控，因此推荐使用栈解法。

代码实现

class Solution {
public:
    string decodeString(string s) {
        stack<int> numStack;
        stack<string> strStack;
        string currentStr = "";
        int num = 0;
        
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                numStack.push(num);
                strStack.push(currentStr);
                num = 0;
                currentStr = "";
            } else if (c == ']') {
                int repeatTimes = numStack.top();
                numStack.pop();
                string prevStr = strStack.top();
                strStack.pop();
                
                string temp = "";
                for (int i = 0; i < repeatTimes; i++) {
                    temp += currentStr;
                }
                currentStr = prevStr + temp;
            } else {
                currentStr += c;
            }
        }
        
        return currentStr;
    }
};

class Solution:
    def decodeString(self, s: str) -> str:
        num_stack = []
        str_stack = []
        current_str = ""
        num = 0
        
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '[':
                num_stack.append(num)
                str_stack.append(current_str)
                num = 0
                current_str = ""
            elif c == ']':
                repeat_times = num_stack.pop()
                prev_str = str_stack.pop()
                current_str = prev_str + current_str * repeat_times
            else:
                current_str += c
        
        return current_str

public class Solution {
    public string DecodeString(string s) {
        Stack<int> numStack = new Stack<int>();
        Stack<string> strStack = new Stack<string>();
        string currentStr = "";
        int num = 0;
        
        foreach (char c in s) {
            if (char.IsDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                numStack.Push(num);
                strStack.Push(currentStr);
                num = 0;
                currentStr = "";
            } else if (c == ']') {
                int repeatTimes = numStack.Pop();
                string prevStr = strStack.Pop();
                
                string temp = "";
                for (int i = 0; i < repeatTimes; i++) {
                    temp += currentStr;
                }
                currentStr = prevStr + temp;
            } else {
                currentStr += c;
            }
        }
        
        return currentStr;
    }
}

var decodeString = function(s) {
    const stack = [];
    let currentStr = '';
    let currentNum = 0;
    
    for (let char of s) {
        if (char >= '0' && char <= '9') {
            currentNum = currentNum * 10 + parseInt(char);
        } else if (char === '[') {
            stack.push([currentStr, currentNum]);
            currentStr = '';
            currentNum = 0;
        } else if (char === ']') {
            const [prevStr, num] = stack.pop();
            currentStr = prevStr + currentStr.repeat(num);
        } else {
            currentStr += char;
        }
    }
    
    return currentStr;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型栈解法递归解法
时间复杂度O(n)O(n)
空间复杂度O(m)O(h + m)

其中：

  • n 是解码后字符串的总长度
  • m 是输入字符串的长度
  • h 是递归调用的最大深度（嵌套层数）

栈解法的空间复杂度主要来自于存储中间状态的栈，递归解法还需要额外的递归调用栈空间。

相关题目