题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
1
2
| 输入：s = "3[a]2[bc]"
输出："aaabcbc"
|
示例 2：
1
2
| 输入：s = "3[a2[c]]"
输出："accaccacc"
|
示例 3：
1
2
| 输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
|
示例 4：
1
2
| 输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
|
提示：
1 <= s.length <= 30s 由小写英文字母、数字和方括号 '[]' 组成s 保证是一个 有效 的输入。s 中所有整数的取值范围为 [1, 300]
题解
核心思路：
- 数字栈（nums）：存储遇到的重复次数
- 字符串栈（chars）：存储当前已解码的字符串
- 遇到
[ 时：将当前字符串和数字分别压栈，并重置临时变量 - 遇到
] 时：弹出栈顶数字（重复次数）和字符串（前缀），进行字符串拼接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
string decodeString(string s) {
stack<string> chars;
stack<int> nums;
string res;
int num = 0;
for (char c : s) {
if (isdigit(c)) // 或者c<='9' && c>='0
{
num = num * 10 + c - '0'; // 拼接多位数（如 "23" -> 2→20+3=23）
} else if (isalpha(c)) {
res += c;
} else if (c == '[') {
chars.push(res);
nums.push(num);
res = "";
num = 0;
} else if (c == ']') {
string tmp = res;
res = chars.top(); // 弹出栈顶字符串（前缀）
chars.pop();
int repeat = nums.top();
nums.pop();
while (repeat-- > 0) {
res += tmp; // 重复拼接子串（如 "abc"×2 → "abcabc"）
}
}
}
return res;
}
};
|
