Keshawn_lu's Blog

Leetcode 394. 字符串解码

字数统计: 655阅读时长: 2 min
2020/05/28 Share

题目简介:

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

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a2[4] 的输入。

示例:

1
2
3
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

思路:

利用栈,遇到数字时则将连续的一串数字压入栈(如326[a],遇到3时,将326找到并作为整体压入栈);

遇到字母或左括号时直接压入栈;

遇到右括号时开始弹出栈顶元素,直到遇到左括号为止,则中间弹出的均是字母,将这些字母保存起来并翻转到正确的顺序。将左括号弹出后,此时栈顶元素为数字,将数字弹出,并根据数字生成新的字符串并压入栈。

最后栈中只会有一系列的字符串,获取后翻转至正确顺序,组合起来返回即可。

tips:

  • 判定字符是否是数字是可用isdigit()函数,判定字符是否是字母时可用isalpha()函数。
  • 字符串转换为数字时可用stoi()函数。
  • char转换为string类型时,可用string (size_t n, char c), 如string(1, 'c')

代码如下:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Solution {
public:

string getdigits(string s, int& ptr){

string res = "";

while(isdigit(s[ptr])){

res += s[ptr++];
}

return res;
}

string getstring(vector<string> in_str){

string res = "";

for(auto s : in_str){

res += s;
}

return res;
}

string decodeString(string s) {

stack<string> temp;
int i = 0;
while(i < s.length()){

//是数字的情况
if(isdigit(s[i])){

string num = getdigits(s, i);
temp.push(num);
}
//字母及左括号的情况
else if(isalpha(s[i]) || s[i] == '['){

temp.push(string(1, s[i]));
i++;
}
else{ //右括号的情况

i++;
vector<string> sub;

while(temp.top() != "["){

sub.push_back(temp.top()); //字母压入数组
temp.pop();
}
temp.pop(); //将左括号弹出

int time = stoi(temp.top()); //此时栈顶元素为次数
temp.pop(); //不能忘了将数字弹出

reverse(sub.begin(), sub.end()); //翻转

string sub_str, time_str = getstring(sub);

while(time != 0){

sub_str += time_str;
time--;
}

temp.push(sub_str);
}
}

vector<string> res;
while(!temp.empty()){

res.push_back(temp.top());
temp.pop();
}

reverse(res.begin(), res.end());


return getstring(res);

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: