题目描述

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

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

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

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

示例 1：

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

具体见题目详解。

算法思路

又是摆烂了很久才写出一道题哈！真的是懒得动了……这个题目其实在大一程设课后习题上就见过，当时也是讲栈这一章节，所以我很快就想起来怎么做的，只不过编码确实花了不少时间，很容易发现，我们需要做的就是遍历字符串，根据数字、字母、[、]分别作出不同的决策即可，决策的目的在于将数字（也可以说是系数）和后面括号里的符号串匹配，难点在于括号嵌套括号，比如 2[a2[b]]，但是如果我们将括号里面的2[b]单独拿出来看，其实是可以先转化成bb来处理的，也就是2[a2[b]]->2[abb]->abbabb，这个过程可以使用递归，或者栈，我以栈为例，具体思路如下：

  1. 如果当前字符s[i]是数字，那么我们应该先将这一串数字型字符恢复成数字，使用如下函数，其实cpp有更简单的方式，比如isdigit和atoi，只不过我积累比较少，用的还是典型的方法，或者说比较笨的办法。接着需要把数字”存”起来，也就是存进系数栈，方便后续拆解字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int calculate(string s, int index) {
    string tmp = "";
    for (int i = index; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            tmp += s[i];
        }
        else {
            break;
        }
    }
    // tmp是字符串类型的数字
    int tmp_length = tmp.length();
    int n = 0;
    int num = 0;
    for(int i = tmp_length - 1; i >= 0; i--) {
        num += (tmp[i] - '0') * pow(10, n);
        n++;
    }
    return num;
}
  1. 如果当前字符s[i]是左括号[或者字母，就直接入字符栈
  2. 如果当前字符s[i]是右括号]，说明我们刚刚遍历了一个“原子化”字符串，也就是k[...]的形式，这时候从系数栈取出k，再从符号栈持续出栈直到[，得到最近的字符串，然后乘以系数k，注意，由于栈是先进后出结构，我们需要将字符串倒序再重新放入栈中。
  3. 重复1,2,3直到遍历结束

完整代码：

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
string decodeString(string s) {
        int length = s.length();
        int i = 0;
        // 如果是数字字符，就进入数字栈，准备累加系数k
        // 如果是[，入栈
        // 如果是],就让字符栈出栈直到遇到[
        // 需要数字栈和字符栈
        stack<int> ks;
        stack<char> ps;
        while (i < length) {
            if (s[i] >= '1' && s[i] <= '9') {
                ks.push(calculate(s, i));
                while (s[i] >= '0' && s[i] <= '9') {
                    i++;
                    continue;
                }
                continue;
            }
            if (s[i] == '[') {
                ps.push(s[i]);
                i++;
                continue;
            }
            if (s[i] == ']') {
                string tmp = "";
                
                // 获取系数
                int k = ks.top();
                ks.pop();

                while (ps.top() != '[') {
                    tmp += ps.top();
                    ps.pop();
                }
                ps.pop(); //弹出[

                // 复制k次tmp
                string ktmp = "";
                for (int i = 0; i < k; i++) {
                    ktmp += tmp;
                }

                // 再将ktmp反转推回去
                reverse(ktmp.begin(), ktmp.end());
                for (int i = 0; i < ktmp.length(); i++) {
                    ps.push(ktmp[i]);
                }
                i++;
                continue;
            }
            if (s[i] >= 'a' && s[i] <= 'z') {
                ps.push(s[i]);
                i++;
                continue;
            }
        }
        string ans = "";
        while (!ps.empty()) {
            ans += ps.top();
            ps.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }

时间复杂度很明显$O(N)$，空间复杂度由于用到线性辅助空间了，所以是$O(N)$。

最后的最后，谁能教教我怎么不摆烂？