描述

题目描述

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

样例解释

首先我们的样例输入是

"3[3[b]]"

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

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

所以最后的输出为

"bbbbbbbbb"

解法一:栈

解题思路

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

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

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

图解代码

20220113155753

20220113155853

20220113155917

20220113160024

20220113160111

20220113160143

20220113160210

代码实现

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)

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