【练习】力扣热题100 字符串解码
题目
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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]
以下是代码，我在每一部分加入了详细的注释，并分块解析其功能和作用。
代码整体解析（带注释）
class Solution {
public:
string decodeString(string s) {
// 定义两个栈：一个用于存储数字，一个用于存储字符串
stack<string> st; // 字符串栈，存储每一层的字符串
stack<int> num; // 数字栈，存储每一层的重复次数
int tnum = 0; // 临时变量，用于解析多位数字
string tst; // 临时变量，用于存储当前解析的字符串
// 遍历输入字符串的每个字符
for (int i = 0; i < s.size(); i++) {
// 1. 处理数字字符
if (isdigit(s[i])) {
// 将字符转换为数字，并累加到 tnum 中
tnum = tnum * 10 + (s[i] - '0');
}
// 2. 处理小写字母字符
else if (islower(s[i])) {
// 将字母追加到当前字符串 tst 中
tst += s[i];
}
// 3. 处理 '[' 字符
else if (s[i] == '[') {
// 将当前数字 tnum 压入数字栈
num.push(tnum);
tnum = 0; // 重置当前数字
// 将当前字符串 tst 压入字符串栈
st.push(tst);
tst = ""; // 重置当前字符串
}
// 4. 处理 ']' 字符
else if (s[i] == ']') {
// 弹出栈顶数字，表示当前层级的重复次数
int temp_num = num.top();
num.pop();
// 弹出栈顶字符串，表示上一层的字符串
string pre = st.top();
st.pop();
// 构建重复后的字符串
string temp_st;
while (temp_num != 0) {
temp_st += tst; // 将当前字符串 tst 重复 temp_num 次
temp_num--;
}
// 将上一层的字符串与重复后的字符串拼接，更新当前字符串 tst
tst = pre + temp_st;
}
}
// 返回最终解码后的字符串
return tst;
}
};
分块解析
1. 初始化部分
stack<string> st; // 字符串栈，存储每一层的字符串
stack<int> num; // 数字栈，存储每一层的重复次数
int tnum = 0; // 临时变量，用于解析多位数字
string tst; // 临时变量，用于存储当前解析的字符串
st：用于存储每一层的字符串。num：用于存储每一层的重复次数。tnum：用于解析多位数字，例如12[a]中的12。tst：用于存储当前解析的字符串。
2. 遍历字符串
for (int i = 0; i < s.size(); i++) {
// 处理当前字符
}
- 遍历输入字符串
s的每个字符s[i]，根据字符的类型执行不同的操作。
3. 处理数字字符
if (isdigit(s[i])) {
tnum = tnum * 10 + (s[i] - '0');
}
- 如果当前字符是数字（
0到9），则将其转换为整数并累加到tnum中。 - 例如，对于字符串
12[a]，tnum会依次变为1和12。
4. 处理小写字母字符
else if (islower(s[i])) {
tst += s[i];
}
- 如果当前字符是小写字母（
a到z），则将其追加到tst中。 - 例如，对于字符串
a2[c]，tst会依次变为a和ac。
5. 处理 [ 字符
else if (s[i] == '[') {
num.push(tnum); // 将当前数字压入数字栈
tnum = 0; // 重置当前数字
st.push(tst); // 将当前字符串压入字符串栈
tst = ""; // 重置当前字符串
}
- 如果当前字符是
[，则表示开始一个新的嵌套层级。 - 将当前的数字
tnum压入num栈。 - 将当前的字符串
tst压入st栈。 - 重置
tnum和tst，以便处理嵌套的内容。 - 例如，对于字符串
3[a2[c]]，当遇到第一个[时：num = [3]st = [""]tnum = 0tst = ""
6. 处理 ] 字符
else if (s[i] == ']') {
int temp_num = num.top(); // 弹出栈顶数字
num.pop();
string pre = st.top(); // 弹出栈顶字符串
st.pop();
string temp_st;
while (temp_num != 0) { // 重复拼接当前字符串
temp_st += tst;
temp_num--;
}
tst = pre + temp_st; // 更新当前字符串
}
- 如果当前字符是
]，则表示结束当前的嵌套层级。 - 弹出
num栈顶的数字temp_num，表示需要重复的次数。 - 弹出
st栈顶的字符串pre，表示上一层的字符串。 - 通过循环将
tst重复temp_num次，并拼接到temp_st中。 - 将
pre和temp_st拼接，得到新的字符串，并赋值给tst。 - 例如，对于字符串
3[a2[c]]，当遇到第一个]时：temp_num = 2pre = "a"tst = "c"temp_st = "cc"tst = "a" + "cc" = "acc"
7. 返回结果
return tst;
- 最终结果存储在
tst中，返回tst。
举例说明：
假设输入字符串为 3[a2[c]]，运行过程如下：
-
初始化：
tnum = 0tst = ""
-
遍历字符：
'3'：tnum = 3'['：num = [3]st = [""]tnum = 0tst = ""
'a'：tst = "a"'2'：tnum = 2'['：num = [3, 2]st = ["", "a"]tnum = 0tst = ""
'c'：tst = "c"']'：temp_num = 2pre = "a"temp_st = "cc"tst = "a" + "cc" = "acc"
']'：temp_num = 3pre = ""temp_st = "accaccacc"tst = "" + "accaccacc" = "accaccacc"
-
返回结果：
tst = "accaccacc"
时间复杂度：
- O(n)，其中
n是解码后字符串的长度。每个字符只会被处理一次。
空间复杂度：
- O(m)，其中
m是栈的深度，取决于嵌套的层数。
总结：
这段代码通过栈实现了字符串解码功能，能够高效地处理嵌套的编码结构。它的时间复杂度为 O(n)，空间复杂度为 O(m)，是一个经典的解法。
原文地址：https://blog.csdn.net/2402_86344613/article/details/145200619
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！