思路
该题就是给定一个编码后的字符串，然后返回解码后的字符串。
由题可知要处理嵌套的情况，即要先解决内层的$k[encoded_string]$，再解决外层，即后进先出，很适合用栈来解决。而且其结构为$k[encoded_string]$，很适合用双栈来解决，一个为数字栈用来存储重复几次，一个为字符串栈用来存储每一层进入 $[$ 时，之前构造的字符串。
代码
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
class Solution
{
public:
string decodeString(string s)
{
string cur_str, pre_str, temp;
stack<int> s_n; // 数字栈，存储重复几次
stack<string> s_s; // 字符串栈，存储前面的字符串
for (size_t i = 0; i < s.size(); ++i)
{
if (s[i] >= 'a' && s[i] <= 'z')
{
cur_str += s[i];
}
else
{
// 处理当前层
if (s[i] == ']')
{
pre_str = s_s.top();
s_s.pop();
int repeatTimes = s_n.top();
s_n.pop();
temp.clear();
for (int i = 0; i < repeatTimes; ++i)
{
temp += cur_str;
}
cur_str = pre_str + temp; // 构造当前处理完的字符串
}
else
{
// 数字
int t_num = 0;
while (s[i] != '[')
{
t_num = t_num * 10 + (s[i] - '0');
++i;
}
s_n.push(t_num);
s_s.push(cur_str);
cur_str.clear();
}
}
}
return cur_str;
}
};
|
zyz