LeetCode 热题 100_字符串解码（71_394_中等_C++）（栈）

题目描述：

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

编码规则为: 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”

示例 4：
输入：s = “abc3[cd]xyz”
输出：“abccdcdcdxyz”

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

题解：

解题思路：

思路一（栈）：

1、通过中括号内嵌中括号的情况，且内嵌的中括号首先计算，可以想到栈的方法解决此问题。
字符串中有四种字符：
① 数字：将数字转换为整数（数字的位数可为多位），称为字符串的重复次数
② 字母：将连续的字母提取出来，连接成字符串
③ 左括号：重复次数和字符串 分别入 数字栈和字符串栈
④ 右括号：弹出状态（出栈），重复n次对应字符串，并连接字符串

例子：s = “3[a2[c]]”
初始状态：k=0 (数字), current=“” (部分字符串), counts栈为空，strings栈为空
① 3 为数字字符，计算连续的数字字符并转换为整数，k=3;
② [ 为左括号，将k=3 和 current=““分别压入 counts栈={3}和strings={””}栈，重置k=0，current=“”
③ a 为字母,计算连接的字母,current=“a”;
④ 2 k=2;
⑤ [ 将k=2 和 current=“a” 分别压入 counts栈={3,2}和strings栈={“”,“a”}，重置k=0，current=“”
⑥ c current=“c”;
⑦ ] 遇到右括号，将counts栈={3,2}中的2出栈，此时current=“c"重复2次 -> current=“cc”,strings栈={”“,“a”}中的"a"出栈,与current连接"acc”
⑧ ] 遇到右括号，counts栈={3}中的3出栈，此时current=“acc"重复3次->current = “accaccacc”,strings栈={”“}中的”“出栈,与current连接"accaccacc”

2、复杂度分析：
① 时间复杂度： O(S)，S代表解码后得出的字符串长度，我们在遍历原字符串的同时会也会将解码后的字符串压入栈中，且进行字符串的连接。
② 空间复杂度：O(S)，S代表解码后得出的字符串长度，栈的总大小最终与 S 相同。

代码实现

代码实现（栈）：

class Solution {
public:string decodeString(string s) {stack<int> counts;  // 用来存储数字 (重复次数)，栈用来存储每个 "[" 对应的重复次数stack<string> strings;  // 用来存储之前的部分字符串，栈用来存储每个 "[" 之前的字符串string current = "";  // 用来存储当前正在构建的字符串（用于存放当前解析出来的子字符串）int k = 0;  // 用来存储当前的重复次数// 遍历字符串中的每个字符for (char c : s) {if (isdigit(c)) {// 如果是数字，构建重复次数 k，直到遇到非数字字符k = k * 10 + (c - '0');  // 处理可能多位的数字} else if (c == '[') {// 如果遇到 '['，说明要开始一个新的子字符串块counts.push(k);  // 将当前的重复次数推入栈中strings.push(current);  // 将当前构建的字符串推入栈中current = "";  // 清空当前字符串，准备构建新的子字符串k = 0;  // 重置重复次数为 0，开始处理新的重复数字} else if (c == ']') {// 如果遇到 ']'，说明当前子字符串块的解析结束string temp = current;   // 将当前的字符串保存到 temp 中current = strings.top(); // 从栈中获取之前的字符串部分strings.pop();  // 弹出栈中的字符串部分int repeatCount = counts.top();  // 从栈中获取重复次数counts.pop();  // 弹出栈中的重复次数// 将当前子字符串重复 repeatCount 次，并拼接到之前的部分for (int i = 0; i < repeatCount; i++) {current += temp;  // 重复并拼接}} else {// 普通字符，直接加入当前正在构建的字符串current += c;}}return current;  // 返回解码后的最终字符串}
};

以思路一为例进行调试

#include<iostream>
#include<stack>
using namespace std;class Solution {
public:string decodeString(string s) {stack<int> counts;  // 用来存储数字 (重复次数)，栈用来存储每个 "[" 对应的重复次数stack<string> strings;  // 用来存储之前的部分字符串，栈用来存储每个 "[" 之前的字符串string current = "";  // 用来存储当前正在构建的字符串（用于存放当前解析出来的子字符串）int k = 0;  // 用来存储当前的重复次数// 遍历字符串中的每个字符for (char c : s) {if (isdigit(c)) {// 如果是数字，构建重复次数 k，直到遇到非数字字符k = k * 10 + (c - '0');  // 处理可能多位的数字} else if (c == '[') {// 如果遇到 '['，说明要开始一个新的子字符串块counts.push(k);  // 将当前的重复次数推入栈中strings.push(current);  // 将当前构建的字符串推入栈中current = "";  // 清空当前字符串，准备构建新的子字符串k = 0;  // 重置重复次数为 0，开始处理新的重复数字} else if (c == ']') {// 如果遇到 ']'，说明当前子字符串块的解析结束string temp = current;   // 将当前的字符串保存到 temp 中current = strings.top(); // 从栈中获取之前的字符串部分strings.pop();  // 弹出栈中的字符串部分int repeatCount = counts.top();  // 从栈中获取重复次数counts.pop();  // 弹出栈中的重复次数// 将当前子字符串重复 repeatCount 次，并拼接到之前的部分for (int i = 0; i < repeatCount; i++) {current += temp;  // 重复并拼接}} else {// 普通字符，直接加入当前正在构建的字符串current += c;}}return current;  // 返回解码后的最终字符串}
};int main(int argc, char const *argv[])
{string str="3[a2[c]]";Solution s;string ans=s.decodeString(str);cout<<ans;return 0;
}

LeetCode 热题 100_字符串解码（71_394)原题链接
欢迎大家和我沟通交流(✿◠‿◠)