394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
示例 1：
输入：s = “3[a]2[bc]”
输出：”aaabcbc”
示例 2：
输入：s = “3[a2[c]]”
输出：”accaccacc”
示例 3：
输入：s = “2[abc]3[cd]ef”
输出：”abcabccdcdcdef”
示例 4：
输入：s = “abc3[cd]xyz”
输出：”abccdcdcdxyz”
这道题目感觉很不好做，我自己的解法很复杂，而且过不去一个测试点：
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
| class Solution {
public:
string decodeString(string s) {
stack<string> st;
int k = 0;
string mode = "";
string currentStr = "";
for (char c : s) {
if (isdigit(c)) {
if (mode != "") {
st.push(mode);
mode = "";
}
k = k * 10 + c - '0';
} else if (isalpha(c)) {
if (k != 0) {
st.push(to_string(k));
k = 0;
}
mode += c;
} else if (c == ']') {
if (stringIsNum(st.top())) {
int num = stoi(st.top());
st.pop();
currentStr = mode;
for (int i = 0; i < num - 1; i++) {
currentStr += mode;
}
st.push(currentStr);
currentStr = "";
mode = "";
} else {
currentStr = st.top();
st.pop();
currentStr += mode;
st.push(currentStr);
currentStr = "";
mode = "";
}
} else if (c == '[') {
if (k != 0) {
st.push(to_string(k));
k = 0;
}
}
}
if (mode != "")
st.push(mode);
currentStr = "";
while (!st.empty()) {
string topStr = st.top();
st.pop();
if (st.empty())
return topStr;
if (stringIsNum(st.top())) {
currentStr = topStr;
int num = stoi(st.top());
st.pop();
for (int i = 0; i < num - 1; i++) {
currentStr += topStr;
}
st.push(currentStr);
currentStr = "";
} else {
currentStr = topStr;
topStr = st.top();
currentStr = topStr + currentStr;
st.pop();
st.push(currentStr);
}
}
return "";
}
private:
bool stringIsNum(string& str) {
try {
int num = std::stoi(str);
return true;
} catch (const std::invalid_argument& e) {
return false;
}
}
};
|
后面我想到了用两个栈来解决这个问题，其中一个栈用来存储字符串段，另一个栈用来存储字符串段重复的次数。接下来的重点就是处理'['、']'符号。
示例1：
对于s = "3[a]2[bc]"：遇到'['的时候，入栈数字以及当前currentStr，并且置空；遇到']'的时候，取字符串段的 top 元素、重复次数栈的 top 元素，然后进行拼接。重复这个过程，currentStr 就是答案。
示例2：
对于s = "3[a2[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
| class Solution {
public:
string decodeString(string s) {
stack<int> counts;
stack<string> strings;
int k = 0;
string currentStr = "";
for (char c : s) {
if (isdigit(c)) {
k = k * 10 + (c - '0');
} else if (isalpha(c)) {
currentStr += c;
} else if (c == '[') {
counts.push(k);
strings.push(currentStr);
k = 0;
currentStr = "";
} else if (c == ']') {
string temp = currentStr;
currentStr = strings.top();
strings.pop();
int count = counts.top();
counts.pop();
for (int i = 0; i < count; i++) {
currentStr += temp;
}
}
}
return currentStr;
}
};
|
不禁要问，为什么可以这样？这里不禁让我想起了离散数学中的群论中的知识点，下面详细分析下。
- 操作数：我们首先定义操作数，很明显这里的操作数为 string 以及 int。
- 操作：这里并没有明确表明操作符号是什么，但是可以推断隐含的操作符。当
int[string] 时，表明要将 string 重复 int 次；当 stringstring 的时候，表明它们需要拼接；至于string int这种运算不存在，因为 int 必须后面跟 string。
因此，遇到'['的时候，这意味着将要计算int[string]，将数字入栈，而且在数字入栈意味着数字前面还有一个 string ，不管这个 string 是否为空，无所谓。当遇到']'的时候，意味着int[string]要进行拼接了。
可以看到，这个道题目无非就是计算int[string]以及stringstring，因此这道题目和+、*混合运算同构。
对于s = "3[a]2[bc]"：可以同构为：s = 3*(a)+2*(bc)；对于s = "3[a2[c]]"，则可以同够为："s = 3*(a+2*(c))"。
以上就是这道题目的内涵了。
总结（gpt4）
将字符串解码问题与离散数学中的概念联系起来，这是一种非常有趣的视角。确实，字符串解码可以看作是对特定运算符（如拼接和重复）的递归运算。这种运算满足一定的结合律，类似于群论中的一些运算属性，尽管这里的操作并不构成严格数学意义上的群，因为群需要满足闭合性、结合律、单位元存在以及每个元素存在逆元等条件。
提供的 C++ 代码示例有效地实现了字符串解码的功能，这里使用了两个栈：一个存储重复的次数（counts），另一个存储到目前为止解析的字符串（strings）。这种方法非常适合处理嵌套的解码结构。
深入理解：
每当遇到 '[' 时，把当前解析到的重复次数和字符串推入各自的栈中，并重置这些变量准备解析括号内的内容。当遇到 ']' 时，从栈中弹出最近的字符串和重复次数，并将解析到的字符串重复相应的次数，再与之前暂存的字符串拼接。
操作符和操作数的对应关系
- 操作数：字符串和整数（重复次数）
- 操作：两种基本操作
int[string]：将字符串重复指定的次数stringstring：将两个字符串拼接起来
代码确实很好地模拟了这一过程，但要注意一点细节上的问题：在字符串解码结束后，如果主字符串（currentStr）后面没有更多的操作，它将直接返回。这种情况下，代码已经正确处理了所有情况。