LeetCode 热题 100_字符串解码（71_394）
- 题目描述：
- 输入输出样例：
- 题解：
- 解题思路：
- 思路一（栈）：
- 代码实现
- 代码实现（栈）：
- 以思路一为例进行调试
题目描述：
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)
