394. 字符串解码

力扣题目链接 (opens new window)

题目描述

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

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

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

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

示例 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]

思路

这道题涉及到嵌套的括号，比如3[a2[c]]，需要先处理内层的2[c]得到cc，再处理外层的3[acc]得到accaccacc。

遇到这种嵌套结构，就应该想到栈了。

用栈怎么做？

我们需要两个栈：

1. 数字栈：存储重复次数
2. 字符串栈：存储当前累积的字符串

遍历字符串时：

• 如果是数字：累积数字（注意可能是多位数，比如100）
• 如果是[：把当前的数字和字符串分别入栈，开始新的一层
• 如果是字母：累积到当前字符串
• 如果是]：说明当前层结束，从栈中弹出数字和字符串，进行解码

具体来说，遇到]时：

1. 从数字栈弹出重复次数k
2. 从字符串栈弹出上一层的字符串prevStr
3. 把当前字符串重复k次，拼接到prevStr后面

这样就完成了一层解码。

举个例子

以3[a2[c]]为例：

遍历到 '3': num = 3
遇到 '[': 数字栈: [3], 字符串栈: [""], 当前字符串 = "", num = 0
遍历到 'a': 当前字符串 = "a"
遍历到 '2': num = 2
遇到 '[': 数字栈: [3, 2], 字符串栈: ["", "a"], 当前字符串 = "", num = 0
遍历到 'c': 当前字符串 = "c"
遇到 ']': 弹出 2 和 "a", 当前字符串 = "a" + "c" * 2 = "acc"
遇到 ']': 弹出 3 和 "", 当前字符串 = "" + "acc" * 3 = "accaccacc"

模拟过程

以 s = "3[a2[c]]" 为例：

栈处理过程：

1. 读取 '3'：num = 3
2. 遇到 '['：数字栈压入3，字符串栈压入""，重置
3. 读取 'a'：curStr = "a"
4. 读取 '2'：num = 2
5. 遇到 '['：数字栈压入2，字符串栈压入"a"，重置
6. 读取 'c'：curStr = "c"
7. 遇到 ']'：弹出2和"a"，curStr = "a" + "c"×2 = "acc"
8. 遇到 ']'：弹出3和""，curStr = "" + "acc"×3 = "accaccacc"

关键点：用两个栈分别存储数字和字符串，遇到'['入栈，遇到']'出栈解码。

解题代码

class Solution {
public:
    string decodeString(string s) {
        stack<int> numStack;      // 数字栈
        stack<string> strStack;   // 字符串栈
        string curStr = "";       // 当前累积的字符串
        int num = 0;              // 当前数字
        
        for (char c : s) {
            if (isdigit(c)) {
                // 累积数字（可能是多位数）
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                // 遇到 '[', 入栈，开始新的一层
                numStack.push(num);
                strStack.push(curStr);
                num = 0;
                curStr = "";
            } else if (c == ']') {
                // 遇到 ']', 出栈，解码当前层
                int repeatTimes = numStack.top();
                numStack.pop();
                string prevStr = strStack.top();
                strStack.pop();
                
                // 当前字符串重复 repeatTimes 次，拼接到上一层
                string temp = "";
                for (int i = 0; i < repeatTimes; i++) {
                    temp += curStr;
                }
                curStr = prevStr + temp;
            } else {
                // 字母，累积到当前字符串
                curStr += c;
            }
        }
        
        return curStr;
    }
};

复杂度分析

• 时间复杂度：O(n)，其中n是解码后字符串的长度，每个字符最多被处理一次
• 空间复杂度：O(n)，栈的空间

其他语言

Python3

class Solution:
    def decodeString(self, s: str) -> str:
        num_stack = []    # 数字栈
        str_stack = []    # 字符串栈
        cur_str = ""      # 当前累积的字符串
        num = 0           # 当前数字
        
        for c in s:
            if c.isdigit():
                # 累积数字（可能是多位数）
                num = num * 10 + int(c)
            elif c == '[':
                # 遇到 '[', 入栈，开始新的一层
                num_stack.append(num)
                str_stack.append(cur_str)
                num = 0
                cur_str = ""
            elif c == ']':
                # 遇到 ']', 出栈，解码当前层
                repeat_times = num_stack.pop()
                prev_str = str_stack.pop()
                
                # 当前字符串重复 repeat_times 次，拼接到上一层
                cur_str = prev_str + cur_str * repeat_times
            else:
                # 字母，累积到当前字符串
                cur_str += c
        
        return cur_str

Java

class Solution {
    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();    // 数字栈
        Stack<String> strStack = new Stack<>();     // 字符串栈
        StringBuilder curStr = new StringBuilder(); // 当前累积的字符串
        int num = 0;                                // 当前数字
        
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                // 累积数字（可能是多位数）
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                // 遇到 '[', 入栈，开始新的一层
                numStack.push(num);
                strStack.push(curStr.toString());
                num = 0;
                curStr = new StringBuilder();
            } else if (c == ']') {
                // 遇到 ']', 出栈，解码当前层
                int repeatTimes = numStack.pop();
                String prevStr = strStack.pop();
                
                // 当前字符串重复 repeatTimes 次，拼接到上一层
                String temp = curStr.toString();
                curStr = new StringBuilder(prevStr);
                for (int i = 0; i < repeatTimes; i++) {
                    curStr.append(temp);
                }
            } else {
                // 字母，累积到当前字符串
                curStr.append(c);
            }
        }
        
        return curStr.toString();
    }
}

Go

func decodeString(s string) string {
    numStack := []int{}      // 数字栈
    strStack := []string{}   // 字符串栈
    curStr := ""             // 当前累积的字符串
    num := 0                 // 当前数字
    
    for _, c := range s {
        if c >= '0' && c <= '9' {
            // 累积数字（可能是多位数）
            num = num * 10 + int(c - '0')
        } else if c == '[' {
            // 遇到 '[', 入栈，开始新的一层
            numStack = append(numStack, num)
            strStack = append(strStack, curStr)
            num = 0
            curStr = ""
        } else if c == ']' {
            // 遇到 ']', 出栈，解码当前层
            repeatTimes := numStack[len(numStack)-1]
            numStack = numStack[:len(numStack)-1]
            prevStr := strStack[len(strStack)-1]
            strStack = strStack[:len(strStack)-1]
            
            // 当前字符串重复 repeatTimes 次，拼接到上一层
            temp := ""
            for i := 0; i < repeatTimes; i++ {
                temp += curStr
            }
            curStr = prevStr + temp
        } else {
            // 字母，累积到当前字符串
            curStr += string(c)
        }
    }
    
    return curStr
}

JavaScript

var decodeString = function(s) {
    const numStack = [];    // 数字栈
    const strStack = [];    // 字符串栈
    let curStr = "";        // 当前累积的字符串
    let num = 0;            // 当前数字
    
    for (const c of s) {
        if (c >= '0' && c <= '9') {
            // 累积数字（可能是多位数）
            num = num * 10 + parseInt(c);
        } else if (c === '[') {
            // 遇到 '[', 入栈，开始新的一层
            numStack.push(num);
            strStack.push(curStr);
            num = 0;
            curStr = "";
        } else if (c === ']') {
            // 遇到 ']', 出栈，解码当前层
            const repeatTimes = numStack.pop();
            const prevStr = strStack.pop();
            
            // 当前字符串重复 repeatTimes 次，拼接到上一层
            curStr = prevStr + curStr.repeat(repeatTimes);
        } else {
            // 字母，累积到当前字符串
            curStr += c;
        }
    }
    
    return curStr;
};

与代码随想录联系

这道题是栈的经典应用，用栈来处理嵌套结构。

我在代码随想录栈章节里，详细讲解了栈的应用场景，建议录友们先看代码随想录栈章节，特别是20.有效的括号，那道题是栈处理括号匹配的基础。

本题的关键点：

1. 两个栈配合使用：数字栈和字符串栈
2. 处理多位数：数字可能是100这种多位数，要累积
3. 遇到]时的解码逻辑：从栈中弹出，重复拼接

另外，这道题也可以用递归做，但用栈更直观。录友们可以两种方法都试试，加深理解。