力扣hot100：394. 字符串解码（递归）

LeetCode：394. 字符串解码

本题容易想到用递归处理，在写递归时主要是需要明确自己的递归函数的定义。
不过我们也可以利用括号匹配的方式使用栈进行处理。

1、递归

• 定义递归函数string GetString(string & s,int & i);
  • 表示处理处理整个number[letter]，处理后i指向’]'之后的一个元素
  • 当letter中有这样的结构时，直接递归处理。
• 定义函数int GetNum(string & s,int & i);
  • 在遇到数字时调用，表示获取s中前缀的数
    

class Solution {
public:
    string decodeString(string s) {
        string target;
        int len = s.size();
        for(int i = 0; i < len;){
            if(s[i] <= 'z' && s[i] >= 'a'){
                target += s[i ++];
            }else{
                target += GetString(s, i);
            }
        }
        return target;
    }
private:
    string GetString(string & s,int & i){//处理number[letter]，处理后i指向']'之后的一个元素
        int num = GetNum(s, i);//获取重复次数
        ++ i;//忽略掉'['
        string str;
        //获取字符串的前面字符位  3[aa2[cd]ff]
        while(s[i] != ']'){
            if(s[i] <= 'z' && s[i] >= 'a'){
                str += s[i ++];
            }else{
                str += GetString(s, i);
            }
        }
        ++ i;//忽略掉']'
        //重复子串
        string substr = str;
        while(--num){
            str += substr;
        }
        return str;
    }
private:
    int GetNum(string & s,int & i){
        int num = 0;
        while(s[i] >= '0' && s[i] <= '9'){
            num *= 10;
            num += s[i ++] -'0';
        }
        return num;
    }
};

2、栈操作

这里可以用不定长数组来模拟栈操作，方便从栈底向栈顶遍历。
我们可以使用类似括号匹配的方法，从左到右遍历字符串，将字符串压入栈中，遇到右括号']'则说明，一定会有一个左括号[匹配，我们可以将这之间的内容弹栈并形成一个整体，再从栈顶中拿出数字联合成一个串，压入栈中，以此类推，直到所有的左右括号匹配完，然后再链接所有串。

• 时间复杂度：$O(S+|s|)$，s是最终字符串长度，|s|是原字符串的长度。
  • 需要遍历原字符串一次，并且每一个字符需要入栈一次，每个字符要出栈一次，字符串需要进行连接，最终连接的长度取决于最终字符串长度。
• 空间复杂度：$O(S)$
  

class Solution {
public:
    string decodeString(string s) {
        vector<string> sta;
        for(auto i : s){
            if(i ==']'){
                string str;
                vector<string> temp;
                //获取[]中的字符串
                while(sta.back() != "["){
                    temp.push_back(sta.back());
                    sta.pop_back();
                }
                for(int j = temp.size() - 1; j >= 0; -- j)
                    str += temp[j];
                //reverse(str.begin(), str.end());//翻转成正序

                sta.pop_back();//弹出'['
                string digitStr;
                //获取数字串
                while(sta.size() > 0 && sta.back() >="0" && sta.back() <= "9"){
                    digitStr += sta.back();
                    sta.pop_back();
                }
                int num = 0;
                //获取数字
                for(int j = digitStr.size() - 1; j >=0; -- j){
                    num *= 10;
                    num += digitStr[j] - '0';
                }
                //将number[letter]结合成一个串
                string substr = str;
                while(--num) str += substr;

                sta.emplace_back(str);

            }else sta.emplace_back(string() + i);
        }
        string ans;
        for(auto & i : sta)
            ans += i;
        return ans;
    }
};

• 注意这两者的区别：
  • for(int j = temp.size() - 1; j >= 0; -- j) str += temp[j];
  • reverse(str.begin(), str.end());//翻转成正序
• 前者并不改变栈中字符串内部顺序，而是改变栈中字符串之间的相对顺序
• 后者会改变栈中字符串的内部顺序