题解

题面描述

给定一个经过编码的字符串，编码规则为：
$k[encodedstring]$
表示其中方括号内部的$encodedstring$正好重复$k$次。输入字符串保证有效，没有额外空格，且所有数字只表示重复次数，不会混淆成其他含义。

思路

本题的核心在于处理嵌套结构的解码问题。我们可以采用栈（stack）的方式解决：

• 当遇到数字时，将数字（可能多位）解析出来，并压入数字栈。
• 当遇到左括号$[$时，将当前结果字符串压入字符串栈，并将结果字符串置空以便处理括号内的新字符串。
• 当遇到右括号$]$时，从字符串栈中取出之前的结果，并从数字栈中取出重复次数，将当前字符串重复对应次数后与之前的字符串拼接。
• 如果遇到普通字符，则直接累加到当前结果中。

这种方法能够很好地处理嵌套和连续编码的情况。

代码分析

1. 数字解析：
   当遇到数字时，需要注意可能存在多位数。用$count = count * 10 + digit$的方式累加计算数字。

2. 栈的使用：
   使用两个栈，一个存放重复次数（$countStack$），一个存放当前结果（$resStack$）。

   • 每遇到$[$，将当前字符串压入$resStack$，然后重置当前字符串。
   • 每遇到$]$，从$resStack$中弹出字符串，并取出数字栈顶的重复次数，将当前字符串重复后拼接到弹出的字符串后。

3. 遍历字符串：
   通过下标遍历整个字符串，根据字符类型分别进行处理，直至遍历完成。

4. ACM模式输入输出：
   主函数中通过输入输出流处理输入，符合ACM竞赛题目的格式要求。

C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    // 解码函数，输入为编码后的字符串，返回解码后的结果字符串
    string decodeString(string s) {
        stack<int> countStack;     // 用于存放重复次数
        stack<string> resStack;    // 用于存放当前已经解析的字符串
        string res = "";           // 当前的结果字符串
        int index = 0;             // 遍历字符串的下标
        while (index < s.size()) {
            if (isdigit(s[index])) {   // 如果遇到数字
                int count = 0;
                // 处理多位数
                while (index < s.size() && isdigit(s[index])) {
                    count = count * 10 + (s[index] - '0');
                    index++;
                }
                countStack.push(count);
            } else if (s[index] == '[') {  // 遇到左括号，开始处理新的子串
                resStack.push(res);
                res = "";
                index++;
            } else if (s[index] == ']') {  // 遇到右括号，回退并构造完整子串
                string temp = resStack.top();
                resStack.pop();
                int repeatTimes = countStack.top();
                countStack.pop();
                // 将当前子串重复$repeatTimes$次，并与之前的字符串拼接
                for (int i = 0; i < repeatTimes; i++) {
                    temp += res;
                }
                res = temp;
                index++;
            } else { // 遇到普通字符，直接累加
                res.push_back(s[index]);
                index++;
            }
        }
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    // 循环读取输入字符串
    while (cin >> s) {
        Solution solution;
        cout << solution.decodeString(s) << "\n";
    }
    return 0;
}

Python

# 定义解码函数，输入为编码后的字符串，返回解码后的字符串
class Solution:
    def decodeString(self, s: str) -> str:
        countStack = []  # 存放重复次数的栈
        resStack = []    # 存放中间结果字符串的栈
        res = ""         # 当前结果字符串
        index = 0        # 当前处理位置的下标
        while index < len(s):
            if s[index].isdigit():  # 如果字符为数字
                count = 0
                # 解析可能的多位数
                while index < len(s) and s[index].isdigit():
                    count = count * 10 + int(s[index])
                    index += 1
                countStack.append(count)
            elif s[index] == '[':  # 遇到左括号，压入当前结果
                resStack.append(res)
                res = ""
                index += 1
            elif s[index] == ']':  # 遇到右括号，回退并构造完整字符串
                temp = resStack.pop()
                repeatTimes = countStack.pop()
                res = temp + res * repeatTimes
                index += 1
            else:  # 普通字符，直接添加到当前结果
                res += s[index]
                index += 1
        return res

if __name__ == "__main__":
    import sys
    # 读取整个输入字符串
    s = sys.stdin.read().strip()
    solution = Solution()
    result = solution.decodeString(s)
    print(result)

Java

import java.util.*;

public class Main {
    // 解码函数，输入为编码后的字符串，返回解码后的字符串
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();  // 用于存放重复次数
        Stack<String> resStack = new Stack<>();       // 用于存放中间结果字符串
        String res = "";  // 当前结果字符串
        int index = 0;    // 当前处理位置的下标
        while (index < s.length()) {
            char ch = s.charAt(index);
            if (Character.isDigit(ch)) {  // 如果字符为数字
                int count = 0;
                // 处理可能的多位数字
                while (index < s.length() && Character.isDigit(s.charAt(index))) {
                    count = count * 10 + (s.charAt(index) - '0');
                    index++;
                }
                countStack.push(count);
            } else if (ch == '[') {  // 遇到左括号，压入当前字符串
                resStack.push(res);
                res = "";
                index++;
            } else if (ch == ']') {  // 遇到右括号，回退并构造完整字符串
                String temp = resStack.pop();
                int repeatTimes = countStack.pop();
                StringBuilder sb = new StringBuilder(temp);
                for (int i = 0; i < repeatTimes; i++) {
                    sb.append(res);
                }
                res = sb.toString();
                index++;
            } else {  // 普通字符，直接累加
                res += ch;
                index++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取输入字符串并输出解码结果
        while (sc.hasNext()) {
            String s = sc.next();
            Main solution = new Main();
            System.out.println(solution.decodeString(s));
        }
    }
}

Leetcode 71.字符串解码-原题链接

题目内容

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

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

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

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

输入描述

一个字符串$k[encodedstring]$

输出描述

输出一个经过解码的字符串

样例1

输入

3[a]2[bc]

输出

aaabcbc

样例2

输入

3[a2[c]]

输出

accaccacc

样例3

输入

2[abc]3[cd]ef

输出

abcabccdcdcdef

样例4

输入

abc3[cd]xyz

输出

abccdcdcdxyz

提示：

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