题意

把压缩过的字符串还原, 压缩过的通过次数[字符串]来表示

范围:

输出长度不会超过50

方法

每次枚举展开

按照题意,我们可以从内到外进行解码.

那第一个出现的右侧括号所包含的内容,就是最内层的.

这样每次解码一块内容更新整个字符串.直到字符串被完全解码为止,就是要求的答案

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string decodeString(string s) {
        string t = s;
        int numst = -1; // 数字起始位置
        int lb = -1; // 括号开始内容
        int cur = 0; // 当前数字的值
        int times = 0; // 当前重复次数
        bool decry = true; // 是否解码过
        while(decry){
            decry = false;
            for(int i = 0;i<t.length();i++){
                //   ???123123123[string]???
                //      |         |     |
                //      numst     lb    i
                if(t[i] == ']'){ // 右括号 每次找首次出现的
                    string newt = "";
                    for(int j = 0;j<numst;j++){ // 前面??? 部分
                        newt+=t[j];
                    }
                    for(int j = 0;j<times;j++){ // 中间循环节
                        for(int k = lb;k<i;k++){
                            newt += t[k];
                        }
                    }
                    for(int j = i+1;j<t.length();j++){ // 后面???部分
                        newt += t[j];
                    }
                    t = newt;
                    decry = true; // 解码过
                    break;
                }
                if(isdigit(t[i]) && cur == 0){ // 记录数字和数字开始位置
                    numst = i;
                    cur*=10;
                    cur+=t[i]-'0';
                }else if(t[i] == '['){
                    lb = i+1; // 记录括号开始的位置
                    times = cur; // 记录重复次数
                    cur = 0;
                }
            }
        }
        return t;
    }
};

复杂度分析

时间复杂度: 因为每次解码都会重新生成字符串,所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 同时持有的变量是常数个,且长度都不大于最后的输出,所以空间复杂度为$O(n)O(n)$

递归遍历

对于字符串一共4种

1. 小写字母,基础字符串的构成
2. 数字,提供的是出现次数
3. 前括号,被循环部分的开始
4. 后括号,被循环部分的结束

所以,可以用 前后括号作为分解点,递归搜索每一层括号

以题目的样例数据3[a]为例子

代码

class Solution {
public:
    
    string gb(string &s,int &i){
        string t = "";
        int cur = 0;
        for(;i<s.length();i++){
            if(s[i] == ']'){ // 后括号返回上层
                return t;
            }
            if(isdigit(s[i])){ // 数字 控制倍数
                cur*=10;
                cur+=s[i]-'0';
            }else if(s[i] == '['){ // 前括号 进入下一层,记录倍数
                i++;
                string r = gb(s,i);
                for(int j = 0;j < cur;j++){
                    t+=r;
                }
                cur = 0;
            }else{ // 字母
                t += s[i];
            }
        }
        return t;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string decodeString(string s) {
        int i = 0;
        // write code here
        return gb(s,i);
    }
};

复杂度分析

时间复杂度: 对于输出的字符来讲,输出的字母每个位置被操作的是常数次,所以总时间复杂度为$O(n)O(n)$

空间复杂度: 主要储存的是输出字符串,所以总空间复杂度为$O(n)O(n)$