描述

题目描述

首先给定我们一个字符串，在这个字符串里面，方括号前面的数字是我们要重复的倍数，方括号里面的字符串是我们要重复，然后让我们输出最后的结果

样例解释

首先我们的样例输入是

"3[3[b]]"

这个我们先从里面的方括号入手，我们先把里面的$bb$扩大三倍，也就是说我们可以得到$bbbbbb$

然后我们在从第二层方括号入手我们可以得到$bbbbbbbbbbbb\; bbb\; bbb$

所以最后的输出为

"bbbbbbbbb"

解法一：栈

解题思路

我们很容易发现其实这个题目的难点就是在于我们的括号嵌套，那我们如何处理呢？

我们可以发现我们的括号嵌套都是从最里面的一层开始的，也就是符合我们栈的结构，先进后出，所以我们可以考虑使用栈来求解这个问题

1. 如果当前当前的数字是数字的话，我们可以存下来，用于后面倍数计算(这里记一下，我们这里的数字都是字符类型的，记得转换为数字类型)
2. 如果是字符，直接加到我们当前的字符串的末尾
3. 如果是左括号，直接入栈，看看能有多少个
4. 如果是右括号，那么我们弹出状态，然后判断

图解代码

代码实现

class Solution {
    string res = "";
    stack<int> num;
    stack<string> alp;
    int multi = 0;
//     res为最后的答案
//     num存储我们的数字
//     alp存储字符
//     multi存储倍数
public:
    string decodeString(string s) {
        for (auto &it : s) {
//             遍历字符串
            if (isdigit(it)) {
//                 判断如果是数字
                multi = multi * 10 + (it - '0');
            } else if (isalpha(it)) {
//                 如果是字母
                res += it;
            } else if (it == '[') {
//                 如果是左括号
                num.push(multi), alp.push(res);
                multi = 0, res = "";
            } else if (it == ']') {
//                 如果是右括号，出栈，然后增添字符串
                string tmp = "";
                int tmp_num = num.top();
                num.pop();
                for (int i = 0; i < tmp_num; i++) tmp += res;
                res = alp.top() + tmp;
                alp.pop();
            }
        }
        return res;
    }
};

时空复杂度分析

时间复杂度： $O(n)O(n)$

理由如下：$nn$代表的是字符串的长度，我们遍历整个字符串，并将括号内的进栈和出栈，所以最后的就是$O(n)O(n)$

空间复杂度： $O(n)O(n)$

理由如下：维护一个栈的大小，栈的大小与我们的字符串长度有关

解法二：递归

解题思路

其实我们可以发现，我们每次遇到括号其实都是存到栈里，然后我们每一次都是再去找我们的这个括号里面的值，其实我们发现我们每一次的操作都是差不多的，那么这个很符合我们递归的特点，所以我们可以考虑使用递归来解决这个问题

代码实现

class Solution {
    int cnt = 0;
public:
    string dfs(string s, int &cnt) {
        string res = "";
        int num = 0;
        while (cnt < s.size()) {
            if (isdigit(s[cnt])) {
//                 如果是数字直接计算大小
                num = num * 10 + (s[cnt] - '0');
            } else if (s[cnt] == '[') {
//                 是左括号递归处理
                string tmp = dfs(s, ++cnt);
                while (num --> 0) res += tmp;
//                 重复num次
                num = 0;
            } else if (s[cnt] == ']') {
//                 右括号退出
                break;
            } else {
//                 字母直接相加
                res += s[cnt];
            }
            ++cnt;
//             下一位
        }
        return res;
    }
    string decodeString(string s) {
        return dfs(s, cnt);
    }
};

时空复杂度

时间复杂度： $O(n)O(n)$

理由如下：$nn$代表的是字符串的长度，我们递归整个字符串，其实也就是把整个字符串跑一边

空间复杂度： $O(n)O(n)$

理由如下：维护一个递归栈的大小，栈的大小与我们的字符串长度有关，最坏就是整个字符串