题解46 | 栈栈！栈栈！我是串串！#字符串解码#

#include <stack>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string ans = "";
    stack<int> nums;
    stack<string> strs;
    int num = 0;
    
    string decodeString(string s) {
        // write code here
        for(int i = 0; i < s.size(); i++){
            if(s[i] >= '0' && s[i] <= '9'){
                num = s[i] - '0';
            }
            else if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
                ans += s[i];
            }
            else if (s[i] == '[') {
                nums.push(num);
                num = 0;
                strs.push(ans);
                ans = "";
            }
            else {
                int copy = nums.top();
                nums.pop();
                for(int j = 0; j < copy; j++){
                    strs.top() += ans;
                }
                ans = strs.top();
                strs.pop();
            }
        }
        return ans;
    }
};

算法基本思路：

1. 遍历字符串s，对于每个字符s[i]，根据不同情况进行处理：

- 如果s[i]是数字，将其转换为对应的整数，并更新num的值；

- 如果s[i]是字母，将其添加到ans字符串中；

- 如果s[i]是左括号'['，将当前的num和ans分别压入nums和strs栈中，并将num和ans重置为空字符串；

- 如果s[i]是右括号']'，从nums和strs栈中取出对应的数字和字符串，将ans重复copy次并添加到取出的字符串后面，更新ans的值。

2. 最终返回ans作为结果。

时间复杂度

O(n)，其中n是字符串s的长度。

空间复杂度

O(n)，主要是由于使用了nums和strs两个栈保存中间结果。