题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例:
s = “3[a]2[bc]”, 返回 “aaabcbc”.
s = “3[a2[c]]”, 返回 “accaccacc”.
s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.
解题思路
解法一：栈
因为括号会有嵌套，所以我们采用栈来首先处理内部，再处理外部。具体规则为：
- 当遇到数字时，将连续的数字解析完并入栈
- 当遇到左括号或者字母时，直接入栈
- 当遇到右括号时，连续出栈直到遇到左括号。将出栈得到的序列反转，并再出栈得到一个重复次数，构造得到新的字符串并入栈
Python 3.6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def decodeString(self, s: str) -> str:
stack = []
count = ""
for char in s:
if char.isdigit():
count += char
elif char == "[":
stack.append(int(count))
count = ""
stack.append("[")
elif char == "]":
cur_str = []
cur_char = ""
while cur_char != "[":
cur_str.append(cur_char)
cur_char = stack.pop()
num = stack.pop()
cur_str.reverse()
stack.append(num * "".join(cur_str))
else:
stack.append(char)
return "".join(stack)
|
执行用时：44 ms
内存消耗：13.6 MB
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
| class Solution {
public:
string getDigit(string& s, size_t& ptr) {
string num = "";
while (isdigit(s[ptr])) {
num.push_back(s[ptr++]);
}
return num;
}
string getString(vector<string>& stack) {
string res;
for (const auto &i : stack) {
res += i;
}
return res;
}
string decodeString(string s) {
vector<string> stack;
size_t ptr = 0;
while (ptr < s.size()) {
char cur_char = s[ptr];
if (isdigit(cur_char)) {
string count = getDigit(s, ptr);
stack.push_back(count);
} else if (isalpha(cur_char) || cur_char == '[') {
stack.push_back(string(1, s[ptr++]));
} else {
++ptr;
vector<string> sub;
while (stack.back() != "[") {
sub.push_back(stack.back());
stack.pop_back();
}
reverse(sub.begin(), sub.end());
stack.pop_back();
int repeat = stoi(stack.back());
stack.pop_back();
string cur_str = getString(sub);
string final_str = "";
while (repeat--) final_str += cur_str;
stack.push_back(final_str);
}
}
return getString(stack);
}
};
|
执行用时：0 ms
内存消耗：6.8 MB
解法二：递归
- 当遇到数字时，将该数字连续解析出来
- 当遇到左括号时，开始递归，并将结果重复多次计入结果变量
- 当遇到右括号时，返回当前结果以及索引值
Python 3.6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def decodeString(self, s: str) -> str:
def dfs(s, idx):
res, repeat = "", 0
while idx < len(s):
if s[idx].isdigit():
repeat = 10 * repeat + int(s[idx])
elif s[idx] == "[":
idx, tmp = dfs(s, idx + 1)
res += repeat * tmp
repeat = 0
elif s[idx] == "]":
return idx, res
else:
res += s[idx]
idx += 1
return res
return dfs(s, 0)
|
执行用时：40 ms
内存消耗：13.5 MB
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
| class Solution {
public:
string dfs(string& s, size_t& i) {
string res = "";
int repeat = 0;
while (i < s.size()) {
if (isdigit(s[i])) {
repeat = 10 * repeat + (s[i] - '0');
} else if (s[i] == '[') {
string tmp = dfs(s, ++i);
while (repeat) {
res += tmp;
--repeat;
}
} else if (s[i] == ']') {
return res;
} else {
res += string(1, s[i]);
}
++i;
}
return res;
}
string decodeString(string s) {
size_t i = 0;
return dfs(s, i);
}
};
|
执行用时：0 ms
内存消耗：6.5 MB
参考
https://leetcode-cn.com/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-leetcode-solution/
https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/