[LeetCode] 394. 字符串解码 (Decode String)

题目描述

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

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

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

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a2[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 {
// cur_char = ']'
++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/