394. Decode String(解码字符串 [ ] 来加密的）_string和char的不同与转换

浅浅的花香味﹌ 2023-02-13 05:42 1阅读 0赞

给定一个编码字符串，返回其解码字符串。  
编码规则为：k\[encoded\_string\]，其中方括号内的encoded\_string被精确重复k次。注意，保证k为正整数。  
您可以假设输入字符串始终有效；没有多余的空格，方括号格式正确等。  
此外，您可以假定原始数据不包含任何数字，并且这些数字仅用于那些重复的数字k。例如，将不会输入3a或2\[4\]。

例子：  
s =“ 3 \[a\] 2 \[bc\]”，返回“ aaabcbc”。  
s =“ 3 \[a2 \[c\]\]”，返回“ accaccacc”。  
s =“ 2 \[abc\] 3 \[cd\] ef”，返回“ abcabccdcdcdef”。

ps：/\* string类中重载了 += 后面加char类型的。注意string是一个类，不能直接用基本类型char赋值！  
\*/  
**思路：**  
要解码这个，用两个栈来保存字符和数字。然后 if else 来逻辑运行，如果是 \[ ，就将之前的res压入到栈，然后初始化res；  
如果是 \] ，就将当前的res变化为解码后的n个字符串，然后将字符串的栈的栈顶部分来加上解码后的字符串，然后弹出该栈顶。得到一个前一个的字符串加上当前的字符串的res；  
如果字符就直接加载res后面。  
这样的话最后的一个一定是 \] ，此时返回res就是对于前一个栈的部分和当前解码后的部分。（最开始压进去的是“”。

时间复杂度O（n）。空间复杂度O（n)  
code:

class Solution { 
    public:
        string decodeString(string s) { 
        string res="";
        int count=0,step=0;
            stack<int> digit;
            stack<string> halfStr;
            
            while(step<s.size()){ 
                if(isdigit(s[step]))
                { 
                           //在string类里应该道重载了+=操作符
                    string num;
                    num+=s[step++];           //char是数据类型，string 是类。不能直接赋值。
                    while(isdigit(s[step])) 
                        num+=s[step++];
                    digit.push(stoi(num));
                }
                //数字就压进去
                else if(s[step]== '[' )
                { 
                    halfStr.push(res);
                    res="";
                    step++;
                }
                else if(s[step]==']')
                { 
                   string tmp=halfStr.top();        //在遇见 ] 的时候，需要将之前的部分加上来到res中。res是[]之中的内容。tmp是之前的内容
                    halfStr.pop();
                    int repeatTimes=digit.top();
                    digit.pop();                //没有弹出数字 
                    for(int i=0;i<repeatTimes; i++)
                       tmp+=res;
                    
                    res=tmp;
                    step++;
                }
                else
                    res+=s[step++];
            }
            return res;
        }
    };