栈-394.字符串解码-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:28:25

4200

代码可运行

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

运行总次数：0

代码可运行

一、题目解析

1、解码规则：k[字符]，将字符重复k次

2、s有效并只包括小写字母和[]

二、算法原理

解法：栈模拟

一个数字栈，一个字符串栈，细节：为了防止越界访问，在字符串栈中先加入一个空串

对于数字，[、]和没有编码的字符串，需要分情况讨论

1、遇到数字：提取数字，放入数字栈中

通过一个变量tmp记录每一位，如果下一位仍是数字，则tmp*10+s[i]-'0'，将原本的个位变为十位，依次这样操作，把数字提取出来

2、遇到‘[’：把‘[’后面的字符串提取出来并放到字符串栈中

借助一个临时的string变量记录字符串

3、遇到‘]’：按照解码规则，将数字栈的栈顶元素和字符串栈的栈顶元素进行解码

top出数字栈和字符串栈的元素，按照规则进行解码

4、遇到单独的字符or字符串：提取字符or字符串并将其放到字符串栈栈顶元素的后面

和提取字符串相同思路

三、代码示例

class Solution {
public:
    string decodeString(string s)
    {
        stack<int> num;
        stack<string> ss;
        ss.push("");
        int i = 0, n = s.size();
        while (i < n)
        {
            //提取数字
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') tmp = tmp * 10 + (s[i++] - '0');
                num.push(tmp);
            }
            else if (s[i] == '[')//提取字符串
            {
                ++i;
                string tmp;
                while (s[i]>='a' && s[i]<='z')
                {
                    tmp += s[i];
                    i++;
                }
                ss.push(tmp);
            }
            else if (s[i] == ']')//解码
            {
                string stmp = ss.top();
                ss.pop();
                int k = num.top();
                num.pop();
                while (k--) ss.top() += stmp;
                i++;//跳过右括号
            }
            else//加入字符串
            {
                string tmp;
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                ss.top() += tmp;
            }
        }
        return ss.top();
    }
};